問題 D: AC自動機
時間限制: 1 Sec 內存限制: 128 MB

[提交][狀態][討論版]
題目描述
天降偉人 PK 又公開了他的新發明：AC自動機——一種可以自動 AC 題目的神秘裝置。

AC自動機刷題的方式非常簡單：首先會瞬間得出題目的正確做法，然后開始寫程序。每秒，AC自動機的代碼生成模塊會有兩種可能的結果：

寫了 x 行代碼；

心情不好，刪掉了之前寫的 y 行代碼。如果 y 大于當前代碼長度，則相當于全部刪除。

對于 NYOJ，存在某個固定的長度 n( n > 0)，一旦AC自動機在某秒結束時積累了大于等于 n 行的代碼，它就會自動提交并 AC 此題，然后新建一個文件（即棄置之前的所有代碼）并開始寫下一題。PK 在 NYOJ 上跑了一天的AC自動機，得到了很多條關于寫代碼的日志信息。他突然發現自己沒有記錄 NYOJ 的 n 究竟是多少。所幸他通過自己 NYOJ 上的 Rank 知道了AC自動機一共切了 k 道題，希望你計算 n 可能的最小值和最大值。
輸入
第一行兩個整數 l, k ( 1<= l <= 10^5,1<= k <= 10^4)，表示刷題機的日志一共有 l 行，一共了AC了 k 題。

第二行 l 個整數 x_1,…, x_l。x_i >= 0 表示寫了 x_i 行代碼，x_i < 0 表示刪除了這道題的 -x_i 行代碼(-10^9<=x_i <=10^9)。
輸出
輸出兩個數 a, b，分別代表 n 可能的最小值和最大值。如果不存在這樣的 n 則輸出 -1。

樣例輸入
4 2
2
5
-3
9
樣例輸出
3 7
提示

樣例一解釋：如果 n = 2 那么刷題機就會切掉 3 題。但如果 n > 7 刷題機最多只能AC 1 題。考慮 n = 4 時發生了什么。

• 第一秒：刷題機寫了 2 行。

• 第二秒：刷題機又寫了 5 行，共有 7 行，提交，自信 AC。

• 第三秒：刷題機刪掉了 3 行，共有 0 行。

• 第四秒：刷題機寫了 9 行，共有 9 行，提交，自信 AC。一共 AC 了兩題。

• /*

• 根據題意需要找第一個等于和最后一個等于

• 我們按我們常規的寫二分到時不太清楚到底取left還是right。

• 這里二分有個技巧：

• 我們二分找最后一個大于（ans1）和第一個小于（ans2），
  之后我們要的答案就等于：
  first_equal = ans1 + 1,
  last_equal=ans2 - 1;

• 
  本題需要注意二分上界是會超過int，上界應該為所有大于0的a[i]

• */
  Ac_code:

#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 1e5+5; LL a[maxn]; LL n,k; LL check(LL now) {LL sum = 0, cnt = 0;for(LL i = 0; i < n; i++){sum += a[i];if(sum >= now){sum = 0;cnt++;}if(sum < 0){sum = 0;}}return cnt; } int main(){scanf("%lld%lld",&n,&k);LL up = 0;for(LL i = 0; i < n; i++){scanf("%lld",&a[i]);if(a[i]>0){up += a[i];}}LL ans1 = 0,ans2 = 0;LL l = 1,r = up;while(l <= r){LL mid = (l+r)>>1;if(check(mid)>k){ans1 = mid;l = mid + 1;}else{r= mid - 1;}}l = 1,r = up;while(l <= r){LL mid = (l+r)>>1;if(check(mid)< k){ans2 = mid;r = mid - 1;}else{l = mid + 1;}}if(check(ans1+1)!= k||check(ans2-1)!= k) puts("-1");else printf("%lld %lld",ans1+1,ans2-1);return 0;}

總結

以上是生活随笔為你收集整理的问题 D: AC自动机（二分,第一个等于和最后一个等于）的全部內容，希望文章能夠幫你解決所遇到的問題。

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