您的位置:首页 > 博客中心 > 互联网 >

P4447 [AHOI2018初中组]分组

时间:2022-05-11 12:26

排序后扫一遍,维护当前分组方案,尽量加入人数少的组。如果某些组再也不可能加入了就统计最小值,如果每组都加入过了相同的实力值就新开一组。

因为组的信息具有单调性,所以可以用双端队列 \(O(n)\) 维护。

code:

#include
using namespace std;
#define Min(x,y)((x)<(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
int a[100005];
deque >deq;
int main()
{
	int n,i,mn;
	scanf("%d",&n);
	mn=n;
	For(i,1,n)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	For(i,1,n)
	{
		if(deq.empty())
		{
			deq.push_back(make_pair(a[i],1));
			continue;
		}
		while(!deq.empty())
		if(deq.front().first+1

本类排行

今日推荐

热门手游