[AHOI2018初中组] 分组
题目描述
小可可的学校信息组总共有 $n$ 个队员，每个人都有一个实力值 $a_i$。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。
但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：$[1, 2, 3, 4, 5]$ 是合法的分组方案，因为实力值连续；$[1, 2, 3, 5]$ 不是合法的分组方案，因为实力值不连续；$[0, 1, 1, 2]$ 同样不是合法的分组方案，因为出现了两个实力值为 $1$ 的选手。
如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。
注意：实力值可能是负数，分组的数量没有限制。
输入格式
输入有两行：
第一行一个正整数 $n$，表示队员数量。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。
输出格式
输出一行，包括一个正整数，表示人数最少的组的人数最大值。
样例 #1
样例输入 #1
7
4 5 2 3 -4 -3 -5
样例输出 #1
3
提示
【样例解释】
分为 $2$ 组，一组的队员实力值是 ${4, 5, 2, 3}$，一组是 ${-4, -3, -5}$，其中最小的组人数为 $3$，可以发现没有比 $3$ 更优的分法了。
【数据范围】
对于 $100%$ 的数据满足：$1\leq n\leq 100000$，$|a_i|\leq10^9$。
本题共 $10$ 个测试点，编号为 $1\sim10$，每个测试点额外保证如下：
| 测试点编号 | 数据限制 |
| $1\sim2$ | $n\leq 6, 1\leq a_i \leq 100$ |
| $3\sim4$ | $n\leq 1000, 1\leq a_i\leq 10^5$ 且 $a_i$ 互不相同 |
| $5\sim6$ | $n\leq 100000, a_i$ 互不相同 |
| $7\sim8$ | $n\leq 100000, 1\leq a_i \leq10^5$ |
| $9\sim 10$ | $n\leq 100000, -10^9 \leq a_i \leq 10^9$ |
算法(贪心 + 二分) O(nlogn)
难点：使得人数最少的组人数最多，输出人数最少的组人数的最大值。
一开始没理解题面，就是这部分：使得人数最少的组人数最多。
说明每个队员入队时需要选择满足连续性的队列中选择长度最短的；
思路
1.由于每组队员的实力值是连续的，同时不能重复
2.用结构体存储，每一组的最后一名队员的实力值以及队员数
3.每个队员入队时，选择满足连续性且队员数最少的组进行入队
4.贪心：每次入队时不用挨个遍历所有满足连续性的组，而只需要倒序遍历已有的组，第一个满足条件的肯定是队员数最少的；
证明：
为什么倒序遍历肯定能得到队员最少的呢？
分析样例
6
before sort: 1 2 3 2 3 4
after sort: 1 2 2 3 3 4
正确答案：3 , [1 2 3] 和 [2 3 4]
错误答案：2 ，[1 2 3 4] 和 [2 3]
(1) 首先我们是对每个队员的实力值，进行从小到大的排序，说明后面的实力值一定是大于等于前面的实力值
(2)那么 i+1个队首元素一定大于或等于第i个队首元素
(3)若某个队员能进入到一个队中，说明该队的最后一名队员的实力值一定比当前队员的实力值小于1（满足连续性），
如果有很多组能接受该队员的加入，说明这些组的队尾元素一定都是相同的；
注意，每个队中的元素是连续的，并且后面队的队首元素大于等于前面队的队首元素，因此当队尾元素相等是，后面的队一定不长于前面的队
因此倒序遍历可以得到当前已有的队列中满足连续性且队长最小的
C++代码
最后一个点$TEL$, $O(n^2)$
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct node {
int num,last;
} s[N];
int a[N];
int ans,idx;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1,a+1+n); //实力值按从小到大进行排序
for(int i = 1; i <= n; i++) {
bool flag = 0; //入队情况
//从后往前遍历找队员数最少的
for(int j = idx; j ; j --) {
//满足连续性
if(s[j].last == a[i] - 1) {
flag = 1; //入队成功
s[j].last = a[i]; //更新队尾元素
s[j].num ++ ; //更新队员数量
break; //已经入队了，退出
}
}
if(!flag) { //没有入队
s[++idx].last = a[i];
s[idx].num = 1; //单独成为一个队伍
}
}
//最后遍历每组，找人数最少的
ans = 0x3f3f3f3f;
for(int i = 1; i <= idx; i++){
if(ans > s[i].num ){
ans = s[i].num;
}
}
cout << ans << endl;
return 0;
}
再优化一下，把每次倒序找的部分用二分替换
找到最后一个小于等于x的数
二分板子：
while(l < r){
int mid = l + r + 1 >> 1;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
最终$AC$代码，$O(nlogn)$
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
struct node {
int num,last;
} s[N];
int a[N];
int ans,idx;
int bsearch(int x){
int l = 1, r = idx;
while(l < r){
int mid = (l + r + 1) >> 1;
//找最后一个小于等于x的数
if(s[mid].last <= x) l = mid;
else r = mid - 1;
}
//当且仅当last == x 时成立
return s[l].last == x ? l : -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a+1,a+1+n); //实力值按从小到大进行排序
for(int i = 1; i <= n; i++){
int op = bsearch(a[i] - 1); //队尾元素为a[i]-1的下标值
if(idx == 0 || op == -1){
s[++idx].last = a[i];
s[idx].num ++;
}
else{
s[op].last = a[i];
s[op].num ++;
}
}
//最后遍历每组，找人数最少的
ans = 0x3f3f3f3f;
for(int i = 1; i <= idx; i++){
ans = min(ans,s[i].num);
}
cout << ans << endl;
return 0;
}
用结构体嫌麻烦，也可以开三个数组
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int a[N]; //实力值
int q[N]; //表示第i个组的最后一个成员的实力值
int s[N]; //表示第i个组的人数
int idx;
int bsearch(int x){
int l = 1, r = idx ;
while(l < r){
int mid = (l + r + 1) >> 1;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
return q[l] == x ? l : -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
//实力值按照从小到大进行排序
sort(a+1,a+1+n);
for(int i = 1; i <= n; i++){
int op = bsearch(a[i] - 1);
if(idx == 0 || op == -1){
q[++idx] = a[i];
s[idx] ++;
}
else {
q[op] = a[i];
s[op] ++;
}
}
int ans = 1 << 30; //嘿嘿又学到了
for(int i = 1; i <= idx ; i++){
ans = min(ans,s[i]);
}
cout << ans << endl;
return 0;
}