原题请见SYZOJ
关于这道题，当时考场上写的时候，觉得贪心就是正解。然而一下考场，学长告诉我说是二分，当时的我too young too naive, 还不知道二分搜索是什么，如今前来补档。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #define LL long long using namespace std; int l, m, n; LL sum, le=0, ri, mid; int d[50005]; inline int get_num() { int ans=0; char tmp; tmp=getchar(); while(tmp>'9'||tmp<'0') tmp=getchar(); while(tmp>='0'&&tmp<='9') { ans=ans*10+tmp-48; tmp=getchar(); } return ans; } inline int check(int a); int main() { cin>>l>>n>>m; for(int i=1;i<=n;i++) { d[i]=get_num(); //d[i]=d[i]-sum; //sum+=d[i]; } n++; d[n]=l; ri=l; int ans; while(le<=ri) { mid=((ri-le)>>1)+le; if(check(mid)<=m) { le=mid+1; ans=mid; } else { ri=mid-1; } } cout<<ans<<"\n"; } inline int check(int a) { LL sum=0; int tmp=0; for(int i=1;i<=n;i++) { if(d[i]-d[tmp]<a) sum++; else tmp=i; } return sum; } |