可以用sort解决第11个点的问题。
by hansen121 @ 2023-07-26 16:24:37
我30分,但第11个点对了。
by hansen121 @ 2023-07-26 16:25:29
第11个点做对做错没关系,反正第11个测试点对了也一分不给
by zhangjunxian1234 @ 2023-08-04 18:29:02
用map记录每个组的最大值 循坏前判断当前这个值 - 1在map中存不存在 不存在直接break
by hhhxxxxx @ 2023-08-06 10:01:40
楼主好巧 我刚好也是这种思路(全程贪心)
连快读都上了,O2也O2了,还是TLE#11,其他全过,map也没有学过,难受啊
``````cpp
#include <iostream>
#include <algorithm>
using namespace std;
inline long long read()
{
register long long res = 0,flag = 1;
register char c = getchar();
while(c < '0' || c > '9') //检查负号
{
if(c == '-')//看他是不是负号
flag = -1;//如果是一会准备乘负一
c = getchar();
}
while(c >= '0' && c <= '9')
{
res *= 10;
res += (c - '0');
c = getchar();
}
return res * flag;
}
struct group
{
long long end = 9145141919810735, len = 0;
};
int main()
{
int n;
n = read();
long long s[n + 10];
group s2[n];
for (int i = 0;i < n;++i)
s[i] = read();
sort(s, s + n);
int top = 0; //指示现在一共有多少队列
//指示目前有没有把当前数接到现有队列之后
for (int i = 0;i < n;++i) //遍历每个队员
{
bool flag = false;
for (int j = top - 1;j >= 0;--j) //贪心算法:把队员每次都加在人最少的队列
{ //从后往前遍历就一定是(能接的)人最少的(因为新队列总是在最后面)
if(s[i] == s2[j].end + 1)
{
++s2[j].end;
++s2[j].len;
flag = true;//已经接进去了不用创建新队列
break;
}
}
if(!flag)//没接
{
s2[top].end = s[i];
s2[top].len = 1;
++top;
}
}
long long ans = 9145141919810735;
for (int i = 0;i < top;++i)
{
if(s2[i].len < ans)
ans = s2[i].len;
}
cout << ans;
return 0;
}
```
by Kasumi_Hakurei @ 2023-08-17 09:23:19
我解决了,做其他二分题目的时候突然想到用类似二分的方法可以做(用一个upper_bound直接找到能插入的最后一个组)
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
inline long long read()
{
register long long res = 0,flag = 1;
register char c = getchar();
while(c < '0' || c > '9') //检查负号
{
if(c == '-')//看他是不是负号
flag = -1;//如果是一会准备乘负一
c = getchar();
}
while(c >= '0' && c <= '9')
{
res *= 10;
res += (c - '0');
c = getchar();
}
return res * flag;
}
int main()
{
int n;
n = read();
long long s[n + 10], m[n + 10] = {0}, sz[n + 10] = {0};//m为组的最大值加一(即加入新数需要的值)
for (int i = 0;i < n;++i)
s[i] = read();
sort(s, s + n);
int top = 0;
for (int i = 0;i < n;++i)
{
int p = upper_bound(m, m + top, s[i]) - m - 1; //检查现在遍历到的这个数能放进
//的最后一个组
if(p >= top || m[p] != s[i])//如果不满足接进去的条件
{//注意:算p>=top是因为top指示的元素是空的,等于和大于top都是越界
//算m[p] 不等于s[i] 是因为如果upper_bound找不到和那个数一模一样的,
//就会插在比那个数小的数的后面一位,这个时候不满足连续数字要求不能插
sz[top] = 1;
m[top] = s[i] + 1;
++top;//不能插入任何一个组,创建一个组
}
else//满足条件就接进去
{
sz[p] += 1;
m[p] += 1;
}
}
long long ans = 9145141919810735;
for (int i = 0;i < top;++i)
if(sz[i] < ans)
ans = sz[i];
cout << ans;
return 0;
}
```
by Kasumi_Hakurei @ 2023-08-22 09:44:11
本来还以为只能用map,提交的时候连map的头文件都加上去了忘了删(
by Kasumi_Hakurei @ 2023-08-22 09:45:03
原来我们的循环方式是$O(n^2)$,现在改成二分查找就是$O(nlog_2n)$,应该过就没问题了
by Kasumi_Hakurei @ 2023-08-22 09:50:33
11点不过不给通过啊
by pbjyeee @ 2024-05-05 22:23:25