BZOJ4590: [Shoi2015]自動刷題機

【傳送門：BZOJ4590】

---

簡要題意：

　　有l秒時間，AC了k道題，給出每秒寫的代碼行數（行數>0表示寫，<0表示刪除，如果剩下的行數不夠刪，則為0），假設行數>=n時能夠提交AC一道題，求出n的最小值和最大值

---

題解：

　　兩個二分找最大值最小值，判斷的時候只要>=mid就提交

　　然后對于不存在的情況，只要沒有記錄過答案就表示不存在

---

參考代碼：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL a[110000];int n;
int check(LL x)
{LL d=0;int s=0;for(int i=1;i<=n;i++){d+=a[i];if(d>=x) s++,d=0;if(d<0) d=0;}return s;
}
int main()
{int k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);LL l=1,r=1LL<<63-1;LL nn=-1,mid,mm=-1;while(l<=r){mid=(l+r)/2;int t=check(mid);if(t<=k){if(t==k) nn=mid;r=mid-1;}else l=mid+1;}l=1,r=1LL<<63-1;while(l<=r){mid=(l+r)/2;int t=check(mid);if(t>=k){if(t==k) mm=mid;l=mid+1;}else r=mid-1;}if(nn==-1||mm==-1) printf("-1\n");else printf("%lld %lld\n",nn,mm);return 0;
}

?