H - Checker FZU - 2041

題意：

一個長度為n的01串，現(xiàn)在能將里面的1移動m次，問最長的連續(xù)0是多長

題解：

沒想出來，看了其他人代碼，就是對于每個0空間進(jìn)行擴(kuò)充，然后記錄每次擴(kuò)充的最大值
關(guān)鍵在于擴(kuò)充的細(xì)節(jié)：
我們每次鎖定一個連續(xù)的0的左右端點(diǎn)（圖中的left和right）
然后看left和right分別向外找最近的0，我們可以通過下圖看出，左側(cè)長度為lena可以找到0，右側(cè)lenb可以找到0，lena<lenb，所以我們移動左側(cè)
每次移動也是緩慢移動，我們讓i和j進(jìn)行交換，然后看left-1（即k的位置）是否為0，如果是0，left就向左移動，相當(dāng)于擴(kuò)大區(qū)間，
為什么要先交換i和j呢？因?yàn)橐獢U(kuò)大范圍，只能先換走j，再換走k，一步一步來，不能著急，每次移動都會消耗步數(shù)

這個思路很妙

代碼：

#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <vector> using namespace std;typedef long long LL; const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int MAXN = 500 + 10; int t, len, step; char G[MAXN], CG[MAXN];int Calc(int left, int right) {strcpy(CG, G);int cnt = step;int low = left - 1, high = right + 1;while (cnt--) {if (low - 1 < 0 && high + 1 >= len) break;for (;;) {if (low - 1 < 0 && high + 1 >= len) break;int lena = INF, lenb = INF;bool yes = false;if (low - 1 >= 0 && CG[low - 1] == '0') {//記錄兩個0之間相隔1的數(shù)量 lena = left - (low - 1);yes = true;} if (high + 1 < len && CG[high + 1] == '0') {lenb = high + 1 - right;yes = true;}if (!yes) {//如果low和high還沒找到0，繼續(xù)向外找 --low;++high;continue;}if (lena < lenb) {//相隔1最少的 swap(CG[low], CG[low - 1]);if (CG[left - 1] == '0') {//查看left是否可以向左擴(kuò)展 --left;}} else {swap(CG[high], CG[high + 1]);if (CG[right + 1] == '0') {++right;}}low = left - 1;high = right + 1;break;}}return right - left + 1; }int main() {scanf("%d", &t);int cas = 0;while (t--) {scanf("%d%d%s", &len, &step, G);int ans = 0;for (int i = 0; i < len;) {if (G[i] == '0') {int j = i;while (j + 1 < len && G[j + 1] == '0') { ++j; }//每次找到連續(xù)0的左右端點(diǎn) ans = max(ans, Calc(i, j));i = j + 1;} else {++i;}}printf("Case %d: %d\n", ++cas, ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的H - Checker FZU - 2041的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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