旅游网站建设步骤,公司网站需要备案吗,如何建立论坛网站,产品推广网站设计H - Checker FZU - 2041
题意#xff1a;
一个长度为n的01串#xff0c;现在能将里面的1移动m次#xff0c;问最长的连续0是多长
题解#xff1a;
没想出来#xff0c;看了其他人代码#xff0c;就是对于每个0空间进行扩充#xff0c;然后记录每次扩充的最大值 关键…H - Checker FZU - 2041
题意
一个长度为n的01串现在能将里面的1移动m次问最长的连续0是多长
题解
没想出来看了其他人代码就是对于每个0空间进行扩充然后记录每次扩充的最大值 关键在于扩充的细节 我们每次锁定一个连续的0的左右端点图中的left和right 然后看left和right分别向外找最近的0我们可以通过下图看出左侧长度为lena可以找到0右侧lenb可以找到0lenalenb所以我们移动左侧 每次移动也是缓慢移动我们让i和j进行交换然后看left-1即k的位置是否为0如果是0left就向左移动相当于扩大区间 为什么要先交换i和j呢因为要扩大范围只能先换走j再换走k一步一步来不能着急每次移动都会消耗步数 这个思路很妙
代码
#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的数量 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继续向外找 --low;high;continue;}if (lena lenb) {//相隔1最少的 swap(CG[low], CG[low - 1]);if (CG[left - 1] 0) {//查看left是否可以向左扩展 --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; }//每次找到连续0的左右端点 ans max(ans, Calc(i, j));i j 1;} else {i;}}printf(Case %d: %d\n, cas, ans);}return 0;
}
