來自FallDream 的博客，未經允許，請勿轉載，謝謝。

---

曾經發明了信號增幅儀的發明家ditoly又公開了他的新發明：自動刷題機--一種可以自動AC題目的神秘裝置。自動刷題機刷題的方式非常簡單：首先會瞬間得出題目的正確做法，然后開始寫程序，每秒，自動刷題機的代碼生成模 塊會有兩種可能的結果： A.寫了x行代碼。 B.心情不好，刪掉了之前寫的y行代碼。（如果y大于當前代碼長度則相當于全部刪除。） 對于每個OJ所有題目，存在某個固定的長度n>0。一旦自動刷題機在某秒結束時積累了大于等于n行的代碼，它就會自動提交并AC此題，然后新建一個文件開始寫下一題。SHTSC在某個OJ上跑了一天的自動刷題機，得到了很多條關 于寫代碼的日志信息。他突然發現自己沒有記錄這個OJ的n究竟是多少。所幸他通過自己在OJ上的Rank知道了機一共切了k道題。希望你計算n可能的最小值和最大值。 n<=10^5? xi<=10^9 很顯然答案滿足單調性，可以直接二分。 #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long #define MN 100000 #define INF 100000000000000LL #define getchar() (*S++) char B[1<<26],*S=B; using namespace std; inline ll read() {ll x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }int n,k,s[MN+5];int check(ll lim) {ll now=0;int sum=0;for(register int i=1;i<=n;i++) now=max(0LL,s[i]+now),now>=lim?(now=0,sum++):0;return sum; } int main() {fread(B,1,1<<26,stdin);n=read();k=read();for(int i=1;i<=n;i++ )s[i]=read();ll l=1,r=INF,ans=-1,mid;while(l<=r){int num=check(mid=l+r>>1);if(num<k) r=mid-1;else if(num==k) ans=mid,r=mid-1;else l=mid+1;}if(ans==-1) return 0*puts("-1");else printf("%lld ",ans);l=1,r=INF,ans=-1;while(l<=r){int num=check(mid=l+r>>1);if(num<k) r=mid-1;else if(num==k) ans=mid,l=mid+1;else l=mid+1;}printf("%lld",ans);return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/bzoj4590.html

總結

以上是生活随笔為你收集整理的[bzoj4590][Shoi2015]自动刷题机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。