解题思路:
使用二分
详见代码
注意事项:
无
参考代码:
#include <bits/stdc++.h> using namespace std; int a[1000100]; int n,m; bool check(int x) { int sum = 1,now = 1; //sum以x为间隔能放sum只,now左区间 for(int i = 1; i <= n; i++) if(a[i]-a[now] >= x) //区间内够间隔长度 { sum++; now = i; //区间左端点拉回 } return sum >= m; //是否比实际牛数量多 } int main() { cin >> n >> m; for(int i = 1; i <= n; i++) scanf("%d",&a[i]); //数据大,避免超时 sort(a+1,a+n+1); //排序 int l = 1,r = a[n]/m+1,mid;//右端点最多是总长度/总数量+1 while(l < r) { //cout << l << " " << mid << " " << r << check(mid) << endl; mid = (l+r)>>1;//>>1表示/2 if(check(mid)) l = mid; if(check(mid+1)) l = mid+1; //避免陷入死循环 else r = mid-1; } cout << l << endl; return 0; }
0.0分
1 人评分
兰顿蚂蚁 (C++代码)浏览:1091 |
C语言训练-排序问题<1> (C语言代码)浏览:599 |
C语言训练-数字母 (C语言代码)浏览:649 |
用筛法求之N内的素数。 (C语言代码)浏览:803 |
简单的a+b (C语言代码)浏览:478 |
矩阵的对角线之和 (C语言代码)浏览:1344 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:455 |
C二级辅导-阶乘数列 (C语言代码)浏览:1686 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:504 |
简单的a+b (C语言代码)浏览:503 |