北京东八区网站建设,国内炫酷的网站设计,自助建站模板,友情链接网址题目链接#xff1a;传送门
将nnn个可重复的整数分为mmm组#xff0c;每组中的数必须连续且不重复#xff0c;使人数最少的组人数最多。 两个最值肯定第一想到二分#xff0c;每次二分出一个值#xff0c;判断在这个值为答案的前提下能否完成分组。 在思考判别函数时发现…题目链接传送门
将nnn个可重复的整数分为mmm组每组中的数必须连续且不重复使人数最少的组人数最多。 两个最值肯定第一想到二分每次二分出一个值判断在这个值为答案的前提下能否完成分组。 在思考判别函数时发现没有必要二分单独依靠人数底线也并不能得到最优解通过贪心就可以直接得到答案。
先将这些数从小到大排序对每个数进行分组group[i]group[i]group[i]表示第iii组的末尾的数可见每组内的数是升序的。 对于一个数a[i]a[i]a[i]遍历现有的所有组如果有一个组的末尾的数group[i]a[i]−1group[i]a[i]-1group[i]a[i]−1则表示这个数可以接在这组的队尾。 但这样并不能保证最优解那我们添加一个条件将这个数加在长度最短的队的队尾即可保证最优。
#include bits/stdc.h
#define A 100010using namespace std;
int n, a[A];
int num, size[A], group[A];int main(int argc, char const *argv[]) {cin n;for (int i 1; i n; i) scanf(%d, a[i]);sort(a 1, a n 1);for (int i 1; i n; i) {int size_min INT_MAX, pos 0; bool flag 0;for (int j 1; j num; j)if (group[j] 1 a[i] and size[j] size_min)pos j, flag 1, size_min size[j];if (flag) size[pos], group[pos] a[i];else group[num] a[i], size[num] 1;}int ans INT_MAX;for (int i 1; i num; i) ans min(ans, size[i]);cout ans endl;
}
