本文共 1784 字,大约阅读时间需要 5 分钟。
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 9129 | Accepted: 4547 |
Description
Input
Output
Sample Input
5 312849
Sample Output
3
Hint
Source
#include#include #include #include #include #include #include #include #include #include using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long LL; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; int x[100005]; int n,m,maxn; int ok(int d) { int p=x[1],cnt=1; for(int i=2;i<=n;i++) if(x[i]-p>=d) { p=x[i]; cnt++; if(cnt>=m) return 1; } return 0; } int main() { while(~scanf("%d %d",&n,&m)) { maxn=0; for(int i=1;i<=n;i++) { scanf("%d",&x[i]); if(x[i]>maxn) maxn=x[i]; } sort(x+1,x+n+1); int l=0,r=maxn+1,mid; while(r-l>1) { mid=(l+r)/2; if(ok(mid)) l=mid; else r=mid; } printf("%d\n",l); //左闭右开区间,输出l; } return 0; }
转载地址:http://kvgsi.baihongyu.com/