題意 ：

• 給一個(gè)x.串，每次操作可以將一個(gè).換成一個(gè)x，問0-k次操作的過程中，連續(xù)的x的數(shù)量最多是多少

思路 ：

• 轉(zhuǎn)換條件，就是我們最多可以將k個(gè).換成x
• 在所有滿足.數(shù)小于等于k的區(qū)間中，最大的區(qū)間長度就是答案；優(yōu)化一下，
• 顯然這會(huì)超時(shí)，我們的優(yōu)化方案是 ：1.前綴和（因?yàn)橐髤^(qū)間內(nèi)的.數(shù)量）；2.滑動(dòng)窗口算法（外層循環(huán)左邊界，每次往右移動(dòng)一個(gè)，內(nèi)層循環(huán)右邊界，找到恰好能讓這個(gè)區(qū)間內(nèi)個(gè)數(shù)小于等于k的最大的右邊界，注意這種循環(huán)方式得到的r是恰好讓區(qū)間內(nèi)數(shù)量大于k的）
• 輸入字符串又沒有給其長度，我們先預(yù)處理出來，注意-1，因?yàn)槲覀兘o它加了個(gè)空格字符

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> #define endl '\n' #define fi first #define se second #define pb push_backusing namespace std; using ll = long long;typedef pair<int, int> PII;int main() {cin.tie(nullptr) -> sync_with_stdio(false);string s; cin >> s;s = " " + s;ll k; cin >> k;ll n = s.size() - 1;vector<int> cnt(n + 1);for (int i = 1; i <= n; i ++ ){if (s[i] == '.') cnt[i] = cnt[i - 1] + 1;else cnt[i] = cnt[i - 1];}ll r = 1, ans = 0;for (ll l = 1; l <= n; l ++ ){while (r <= n && cnt[r] - cnt[l - 1] <= k)r ++ ;ans = max(ans, r - 1 - l + 1);}cout << ans << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Longest X 贪心，滑动窗口，前缀和（400）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。