查看原题请戳这里
输出人数最少的组人数的最大值。
看到这句话我就直接去想二分答案怎么做了……
结果check函数没想出来怎么写，不用二分答案的方法倒是有了（虽然说用了一下二分查找）……
这道题其实可以直接去模拟。
我们先把每个人的实力值进行排序，然后从按能力值从小到大依次进行分组。我们通过维护一个单调上升的序列$q$来求解。其中$q$中的每一个元素带表一个分组中能力值的最大值，不难发现，当且仅当$q[j]=a[i]-1$时，我们才可以把第$i$个人分入第$j$个组中。在进行分组的同时，我们还需要一个和$q$数组对应的$sum$数字来记录每个组内的人数。在维护时，我们要保证在$q$相同的情况下，$sum$数组是从小到大排序的，这样当我们就可以直接在满足$q[j]=a[i]-1$时选择最大的$j$，插入到第$j$组中。（即每次都将正在进行分组的人分到可加入的组中人数最少的一组，总而满足人数最少组的人数最大）。
当我们对第$i$个人进行分组时，具体操作如下：
- 在序列$q$中查找$q[j]=a[i]-1$（因为$q$时单调的，我们选择用二分查找来完成这一步）
- 若存在$q[j]=a[i]-1$，则选取最大的$j$，将第$i$个人插入第$j$组中，同时更新$sum$数组。
- 若不存在$q[j]=a[i]-1$，则在$q$的末尾加入新的元素$a[i]$，表示吧第$i$个人分入一个新的组中，这个组中能力值的最大值为$a[i]$。由于我们按能力值从小到大进行分组，故此时可以保证$a[i]$是$q$中最大的元素，从而保证了$q$的单调性。
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define qwq printf("qwq\n");
using namespace std;
int read() {
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
int n, cnt, ans, a[100005], q[100005], sum[100005];
bool mysort(int a,int b) {return a < b;}
int search(int k) {
int l =1 , r = cnt, mid;
while(l <= r) {
mid = (l + r) >> 1;
if(q[mid] == k) return mid;
if(q[mid] < k) l = mid + 1;
if(q[mid] > k) r = mid - 1;
}
return 0;
}
int main() {
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
sort(a + 1, a + n + 1, mysort);
for(int i = 1; i <= n; i++) {
int k = search(a[i] - 1);
if(!k) {
q[++cnt] = a[i];
sum[cnt] = 1;
continue;
}
while(q[k + 1] == q[k] && k < cnt) k++;
q[k]++; sum[k]++;
while(sum[k] < sum[k + 1] && k < cnt) {
int stp = q[k];
q[k] = q[k + 1];
q[k + 1] = stp;
stp = sum[k];
sum[k] = sum[k + 1];
sum[k + 1] = stp;
k++;
}
}
ans = INF;
for(int i = 1; i <= cnt; i++) ans = min(ans, sum[i]);
printf("%d\n", ans);
return 0;
}
|
