解题思路:
使用二分
详见代码
注意事项:
无
参考代码:
#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语言训练-阿姆斯特朗数 (C语言代码)浏览:852 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:468 |
P1002 (C语言代码)浏览:980 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:734 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:751 |
字符串的输入输出处理 (C语言代码)浏览:945 |
简单的a+b (C语言代码)浏览:631 |
WU-格式化数据输出 (C语言代码)浏览:1755 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:711 |
K-进制数 (C语言描述,蓝桥杯)浏览:925 |