当前位置: 代码迷 >> 综合 >> UVA 111100 The Trip, 2007 贪心 *
  详细解决方案

UVA 111100 The Trip, 2007 贪心 *

热度:49   发布时间:2023-09-23 05:12:29.0

题目地址:http://vjudge.net/problem/UVA-11100

题目求最小分组,所以肯定使用二分的方法

那么变成,分为k个分组可不可行的问题

数据量是1e4,所以只能是nlogn以下的算法

自己猜想:

1)注意到题目中表明n不超过1e6 ,用个数组保存数的个数,如1,1,2,2,2,3表示成2,3,1,正好能2组,但不知道怎么判断

2)1)想半天,感觉贪心靠谱点

想贪心:

1)作为每组的第一个数肯定越小越好,第二个肯定也比第一个大一点的但也是越小越好,数据结构:用map<int,int> cnt 表示某个数有几个


程序框架:

1)map读入数据,同时计数 插入需要O(nlogn)

2)二分1~有n个数,Check(k)函数判断k组可不可行 ,二分要logn,判断要(k*n/k),k组每组n/k个


想了几个小时,以为每组个数都要一样,WR

又改成不一样,结果还是WR,因为贪心策略有明显漏洞


看题解...顺利AC

二分个屁..

思路如下:因为每个背包的个数不一定一样,那么肯定同等大小的包的数量的最大就是答案

因为至少差k个,所以输出时每隔k个输出肯定是不同大小的,真机智

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=1000000+5;
int n,a[maxn],cnt[maxn];
int main(int argc, char const *argv[])
{bool first=true;while(scanf("%d",&n)==1&&n){int Max=0;memset(cnt,0,sizeof(cnt));REP(i,0,n-1){scanf("%d",&a[i]);cnt[a[i]]++; Max=max(Max,cnt[a[i]]);}sort(a,a+n);if(!first) printf("\n");else first=false;printf("%d\n", Max);REP(i,0,Max-1){for(int j=i;j<n;j+=Max) printf("%s%d",j==i?"":" ",a[j]);printf("\n");}}return 0;
}







  相关解决方案