首页 > 代码库 > The trip(Uva 11100)
The trip(Uva 11100)
题目大意:
给出n个数,要求将其分成最少的递增序列,保证序列最少的同时要使得序列长度的最大值最小。 n<=10000
题解:
1.我是直接看着《训练指南》里的中文题面的,lrj似乎忘记提“保证序列最少的同时要使得序列长度的最大值最小”这个条件了,WA到死。。我的做法是统计每个数出现的次数,然后每次尽可能构造一个最长的序列,这样能保证序列个数最少,但是显然不满足第二个条件。
2.由于之前WA到死,就很没志气的百度了题解..然后瞄到一眼最少的序列个数就是出现次数最多的那个数的出现次数(记为m)..然后突然就会做了。先把所有数从小到大排序,然后第0个数分给第0个序列,第1个数分给第1个序列....第i个数分给第(i mod m)个序列。这样显然符合题意,而且每个序列的长度非常平均,序列长度的最大值一定是最小的。
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 #include <map> 8 #include <cstdlib> 9 #include <set>10 using namespace std;11 12 #define X first13 #define Y second14 #define N 1001015 typedef long long ll;16 typedef pair<int,int> pii;17 18 int n,m,tot;19 int v[N],b[N],cnt[N];20 vector<int> g[N];21 22 int main()23 {24 //freopen("in.in","r",stdin);25 //freopen("out.out","w",stdout);26 27 while (scanf("%d",&n))28 {29 if (n==0) break;30 for (int i=0;i<n;i++) scanf("%d",&v[i]);31 sort(v,v+n); tot=m=0;32 33 for (int i=0;i<n;i++)34 {35 if (i==0 || v[i]!=v[i-1]) cnt[tot++]=1;36 else cnt[tot-1]++;37 } 38 for (int i=0;i<tot;i++) if (cnt[i]>cnt[m]) m=i;39 m=cnt[m];40 printf("%d\n",m);41 for (int i=0;i<m;i++) g[i].clear();42 for (int i=0;i<n;i++) g[i%m].push_back(v[i]);43 44 for (int i=0;i<m;i++)45 {46 for (int j=0;j<g[i].size();j++)47 {48 printf("%d",g[i][j]);49 printf("%c",j==g[i].size()-1? ‘\n‘:‘ ‘);50 }51 }52 }53 54 return 0;55 }
The trip(Uva 11100)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。