首先输入一个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(" ");
你可以用这个代码把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 ",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** ",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 ",i); 40 else 41 printf("%d ",i); 42 p[i]--; 43 } 44 } 45 // } 46 47 return 0; 48 }
View Code
c格式代码：
1 #include <stdio.h> 2 #include<string.h> 3 #define maxn 10000000+5 4 int v[maxn],w[maxn],p[maxn]; 5 int max(int x,int y){ 6 if(x>y) return x; 7 else return y; 8 } 9 int main(){ 10 int n,a,maxx=0; 11 scanf("%d",&n); 12 for(int i=1;i<=n;++i) 13 { 14 scanf("%d",&a); 15 v[a]=1; 16 maxx=max(maxx,a); 17 } 18 int ans=0,i; 19 for(i=1;i<=maxx;++i){ 20 if(v[i]){ 21 w[i]=w[i-1]+1; 22 } 23 else { 24 p[w[i-1]]++; 25 ans=max(ans,w[i-1]); 26 } 27 } 28 p[w[i-1]]++; 29 ans=max(ans,w[i-1]); 30 31 for(int i=1;i<=ans;++i){ 32 while(p[i]) 33 { 34 if(i==ans && p[i]==1) 35 printf("%d ",i); 36 else 37 printf("%d ",i); 38 p[i]--; 39 } 40 } 41 return 0; 42 }
View Code
生成数据的代码：
1 #include <bits/stdc++.h> 2 #include<fstream> 3 #define INF 0x3f3f3f3f 4 using namespace std; 5 const int maxx=1e7; 6 const int minn=1; 7 const int N=4; 8 int w[maxx+5],p[maxx+5],v[maxx+5]; 9 string getname(int i, string a) 10 { 11 stringstream ss; 12 ss << i << a; 13 return ss.str(); 14 } 15 int int_rand(int min,int max) 16 { 17 return int(min+rand()%(max-min)); 18 } 19 int main(){ 20 srand((unsigned)time(NULL)); //随机种子 21 //for(int i=1;i<=N;++i){ 22 string name1, name2; 23 //name1 = getname(i, ".in"); 24 //name2 = getname(i, ".out"); 25 ofstream fp2("1.out", ios::out); 26 ofstream fp1("1.in", ios::out); 27 //fp2.open(name2, ios::out); 28 29 int n=int_rand(minn,maxx),a,maxn=0; 30 //printf("%d ",n); 31 fp1<<n; 32 fp1<<(" "); 33 for(int i=1;i<=n;++i){ 34 a=int_rand(minn,maxx); 35 //printf("%d ",a); 36 v[a]=1; 37 maxn=max(maxn,a); 38 if(i!=n) { 39 fp1<<a<<" "; 40 } 41 else { 42 fp1<<a<<" "; 43 } 44 } 45 46 //memset(w,0,sizeof(w)); 47 //memset(v,0,sizeof(v)); 48 //memset(p,0,sizeof(p)); 49 //int a; 50 //for(int i=1;i<=n;++i) 51 //{ 52 // scanf("%d",&a); 53 // v[a]=1; 54 // maxx=max(maxx,a); 55 //} 56 int ans=0,i; 57 for(i=1;i<=maxn;++i){ 58 if(v[i]){ 59 w[i]=w[i-1]+1; 60 } 61 else { 62 p[w[i-1]]++; 63 ans=max(ans,w[i-1]); 64 } 65 } 66 p[w[i-1]]++; 67 ans=max(ans,w[i-1]); 68 69 for(int i=1;i<=ans;++i){ 70 while(p[i]) 71 { 72 if(i==ans && p[i]==1) 73 fp2<<i<<" ";//,printf("%d ",i); 74 else 75 fp2<<i<<" ";//,printf("%d ",i); 76 p[i]--; 77 } 78 } 79 80 81 fp1.close(); 82 //fp2.close(); 83 // } 84 }
View Code
支付宝扫一扫
微信扫一扫
