非常非常非常有意思的一道題,正好寫一下做題思路

對于到不了的情況,那就是存在連續>0的區間,該區間和>=m,這樣不管怎么補血一定過不去,cin的時候,就可以判斷

最開始我以為是貪心,發現當前區間走不過去那就返回上一個0點補血,但就是過不去

突然我發現這個樣例很有意思

11 7

0? 1? 0? 1? 1? 1? ?0? 1 1 1 0

按照我一開始想的貪心,在走最后那段111,是回倒數第二個0補血,這樣補血是+4,可正確的做法是回正數第二個補血,這樣只需要回+1,這就可以看出,純貪心回上一個0補血是存在漏洞的

那該怎么確定回哪個0補血呢???

這里很容易想到,那肯定是越靠前的0補血越好啊,因為這樣可以省去中間一些1回血加的時間

到這里問題就轉化為,怎么確定哪個0可以補血

這里反而用到了貪心,就是前面說的,越靠前補血越好,也就是找左邊第一個能補血的0點

用前綴和算區間扣血數,二分查找,當前行,那就往左找,當前不行那就往右找

二分 + 前綴和還是很常用的

具體的直接看代碼就行

// Problem: 阿里馬馬與四十大盜
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/72980/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Date: 2024-03-03 09:58:36
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#include<unordered_map>
#define endl '\n'
#define int int64_t
using namespace std;
int a[100005],s[100005],rec[100005],cnt,n,m;
int check(int si) {//找到第一個 si - m < spos的點int l = 1, r = cnt,ans;while (l <= r) {int  mid = l + r >> 1;if (si - m >= s[rec[mid]]) l = mid + 1;else ans = mid ,r = mid - 1;}return rec[ans];
}
void solve() {cin >> n >> m;for (int i = 1,sum = 0; i <= n; ++i) {cin >> a[i];if (a[i]) {sum += a[i];if (sum >= m) {cout << "NO\n";return;}}else sum = 0;s[i] = s[i - 1] + a[i];}map<int,int>p;p[1] = m;//當前血量rec[++cnt] = 1;int tot = 0;//sum是扣除血量的總和for (int i = 2,sum = 0; i < n;++i) {if (a[i] == 0) {p[i] = m - sum;rec[++cnt] = i;}sum += a[i];if (sum >= m) {//找補血點,貪心就是貪,最好要從最遠點開始補血,越遠越好//怎么判斷這個補血點行不行呢??//s[i] - s[pos] < mint pos = check(s[i]);tot += m - p[pos];sum = 0;i = pos;}/*cout << "sum = " << sum << endl;cout << "tot = " << tot << endl;*/}cout << tot + n - 1 << endl;
}
signed main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t = 1;while (t--) {solve();}return 0;
}