解题思路:去ACwing那个网站里面写这个题,测试点真的坑,这个网站测试数据没卡这种,比如输入3个 2,6, 12。如果是按照找所以中差值最小的作为公差,就GG了,看了一下大佬的思路,用所有的数跟第一个数做差,然后不停的比较它们的最大公约数gcd。这样就不会卡这种测试数据。不过按照一般的思路也能对百分之90的测试数据。
注意事项:除数不能为0,几次运行错误,我还以为是我数组开小了....
参考代码:
#include<bits/stdc++.h> using namespace std; long a[100000]; int gcd(int x,int y) { if(y!=0) { gcd(y,x%y); } else { return x; } } int main() { int n,i; long long minn = 9999999,maxx = -1; cin>>n; for(i = 0;i<n;i++) { cin>>a[i]; if(minn>a[i]) { minn = a[i]; } if(maxx<a[i]) { maxx = a[i]; } } int cha = 0,c; sort(a,a+n); for(i = 1;i<n;i++) { cha = gcd(cha,a[i]-a[0]); } int ans; if(cha == 0) { ans = n; } else { ans = (maxx-minn)/cha + 1; } cout<<ans<<endl; return 0; }
//一般的写法
#include<bits/stdc++.h> using namespace std; int a[100000]; int main() { int n,i; cin>>n; for(i = 0;i<n;i++) { cin>>a[i]; } sort(a,a+n); int minn = a[0],maxx = a[n-1],d = 1e8,ans; for(i = 0;i<n;i++) { if(i == n-1) { break; } if((a[i+1]-a[i])<d) { d = a[i+1] - a[i]; } } if(d!=0) { ans = (maxx-minn)/d+1; } else { ans = n; } cout<<ans<<endl; return 0; }
0.0分
1 人评分
C二级辅导-公约公倍 (C语言代码)浏览:2122 |
大神老白 (C语言代码)浏览:713 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1049 |
C二级辅导-公约公倍 (C语言代码)浏览:1508 |
C语言考试练习题_排列 (C语言代码)浏览:1315 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:583 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:665 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:624 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)万恶的long long浏览:875 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:598 |