首先输入一个n，之后输入n个数a(1<=a<=1e7)，对这n个数排序后，你需要找到所有的它们连续的长度。把这些连续的长度排序后输出
输入
输入：
8
1 5 2 7 4 5 7 1
输出
输出：
1 2 2
样例解析：
将上面数排序得：
1 1 2 4 5 5 7 7
去重后 ：
1 2 4 5 7
连续长度：
2 2 1
因为1 2 4之间少一个3去连接，所以1 2和4之间要断开。又因为4 5和7之间少一个6来连接，所以5和7直之间要断开
结果排序后：
1 2 2
题解：
因为n最大是是1e7，而且程序必须在1s内得到答案。所以我们这里肯定要使用O(n)复杂度的木桶排序
对于：1 5 2 7 4 5 7 1 这一组数据
如果使用木桶排序的话数组至少要开到v[9],因为用木桶排序用的数据本身当v数组的下标
v数组： 0 1 2 3 4 5 6 7 8 9 //数组下标
处理一下v数组： 0 1 1 0 1 1 0 1 0 0 //这里的1代表这个下标在输入的数据中出现过，0代表没有出现过。比如v[2]=1,就表示2这个数在我们输入的数据中
代码：
#include <stdio.h> #include<string.h> #include <iostream> #define INF 0x3f3f3f3f using namespace std; const int maxn=1e7+5; int v[maxn],w[maxn],p[maxn]; int main() { int n,a,maxx=0; scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&a); v[a]=1; maxx=max(maxx,a); } }
这样处理过之后我们发现完成了去重和排序
for(int i=1;i<=maxx;++i) { if(v[i]>0) { printf("%d ",i); } } printf("\n");
你可以用这个代码把v数组打印出来结果会是1 2 4 5 7
之后我们就要求它的连续长度，这个时候就新定义一个数组w和p
int ans=0,i; for(i=1;i<=maxx;++i){ if(v[i]){ w[i]=w[i-1]+1; } else { p[w[i-1]]++; ans=max(ans,w[i-1]); //我们把 } } 下标 ：0 1 2 3 4 5 6 7 8 9 v中的值：0 1 1 0 1 1 0 1 0 0 w初始值：0 0 0 0 0 0 0 0 0 0 处理后w：0 1 2 0 1 2 0 1 0 0 把w[1,7]这个下标内的，所有0之前的值都存起来，因为它就是那个连续长度 2 2 1 这个1不在0之前但是它也是连续长度，我们也要把它取出来 第一个2是{1，2}这两个数的两个数的连续长度。 第二个2是{4，5}这两个数的连续长度 第三个数1是{7}这1个数的连续长度
这样的话，我们就会得到2 2 1这个结果，但是我们还要对它排序后再输出。这里又要用到木桶排序
但是我已经把它们放在木桶p里面了
int ans=0,i; for(i=1;i<=maxx;++i){ if(v[i]){ w[i]=w[i-1]+1; } else { //else就是出现了断点0 p[w[i-1]]++; //把这个数用木桶存起来 ans=max(ans,w[i-1]); //找到这个木桶的右端点 ，以便我们下一步输出的时候去枚举 } //因为木桶排序是把这个数当作下标，所以要找右端点只需要看你需要用到的最大下标是多少 }
下标： 0 1 2 3 4
p初始值：0 0 0 0 0
处理后p：0 1 2 0 0
之后就打印出就可以了，注意格式：
p[w[i-1]]++; ans=max(ans,w[i-1]); //不加这两行代码的话，这个样例中的1，就会没有放到木桶p中 for(int i=1;i<=ans;++i){ while(p[i]) { if(i==ans && p[i]==1) printf("%d\n",i); else printf("%d ",i); p[i]--; } }
总代码：用c++格式提交
1 #include <stdio.h> 2 #include<string.h> 3 #include <iostream> 4 #define INF 0x3f3f3f3f 5 using namespace std; 6 const int maxn=1e7+5; 7 int v[maxn],w[maxn],p[maxn]; 8 int main(){ 9 //while(1){ 10 // memset(w,0,sizeof(w)); 11 // memset(v,0,sizeof(v)); 12 // memset(p,0,sizeof(p)); 13 int n,a,maxx=0; 14 scanf("%d",&n); 15 for(int i=1;i<=n;++i) 16 { 17 scanf("%d",&a); 18 v[a]=1; 19 maxx=max(maxx,a); 20 } 21 int ans=0,i; 22 for(i=1;i<=maxx;++i){ 23 if(v[i]){ 24 w[i]=w[i-1]+1; 25 } 26 else { 27 //printf("%d**\n",w[i-1]); 28 p[w[i-1]]++; 29 ans=max(ans,w[i-1]); 30 } 31 } 32 p[w[i-1]]++; 33 ans=max(ans,w[i-1]); 34 35 for(int i=1;i<=ans;++i){ 36 while(p[i]) 37 { 38 if(i==ans && p[i]==1) 39 printf("%d\n",i); 40 else 41 printf("%d ",i); 42 p[i]--; 43 } 44 } 45 // } 46 47 return 0; 48 }
原文：https://www.cnblogs.com/kongbursi-2292702937/p/11628424.html
