題意 ：

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

思路 ：

• 轉換條件，就是我們最多可以將k個.換成x
• 在所有滿足.數小于等于k的區間中，最大的區間長度就是答案；優化一下，
• 顯然這會超時，我們的優化方案是 ：1.前綴和（因為要求區間內的.數量）；2.滑動窗口算法（外層循環左邊界，每次往右移動一個，內層循環右邊界，找到恰好能讓這個區間內個數小于等于k的最大的右邊界，注意這種循環方式得到的r是恰好讓區間內數量大于k的）
• 輸入字符串又沒有給其長度，我們先預處理出來，注意-1，因為我們給它加了個空格字符

#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; }

總結

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

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