自动搬运

查看原文

来自洛谷，原作者为

	lmz105 已经看到我们学校对面的在学校（直线距离不超过100米）向我招手|一个平平无奇普普通通的FVV(以刷水题为生,永远不做外国题（已取消，because不会一直UKE了（已取消，because又UKE了）））

搬运于2025-08-24 23:16:04，当前版本为作者最后更新于2025-05-15 15:12:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

对于所有日程均为工作日的情况，直接判断可调休天数是否大于等于 $2$，是的话输出调休天数，否则输出 $0$。

对于其他情况，我们考虑每调休一天可以增加几天充实休假日，可以发现有三种情况：

• 两天单独一天的休息日，且它们之间只需要调休一天就可以链接在一起，用字符串表示为 01010 -> 01110，这种情况可以增加 $3$ 天。
• 单独一天的休息日，在它的前一天或后一天调休，用字符串表示为 010 -> 110 或 010 -> 011，这种情况可以增加 $2$ 天。
• 在一段充实休假日前面或后面调休，用字符串表示为 110 -> 111 或 011 -> 111，这种情况可以增加 $1$ 天。

接下来只要让增加的充实休假日最多就行了。

代码

#include <bits/stdc++.h>
#define ll long long
//#define rw() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifndef rw()
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

namespace FX {
	template<typename T> inline void r(T &in) {
		in = 0;
		bool bo = 0;
		char ch = getchar();
		while (!isdigit(ch)) {
			bo ^= (ch == '-');
			ch = getchar();
		}
		while (isdigit(ch))
			in = (in << 1) + (in << 3) + (ch ^ 48), ch = getchar();
		if (bo) {
			in = -in;
		}
	}
	template<typename T> inline void w(T out) {
		static char op[25];
		int top = 0;
		if (out < 0) {
			putchar('-');
			do {
				op[++top] = -(out % 10) + 48, out /= 10;
			} while (out);
		} else {
			do {
				op[++top] = out % 10 + 48, out /= 10;
			} while (out);
		}
		while (top)
			putchar(op[top--]);
		putchar('\n');
	}
	template<typename T, typename... Ts> inline void r(T &in, Ts &... ins) {
		r(in), r(ins...);
	}
	template<typename T, typename... Ts> inline void w(T out, Ts... outs) {
		w(out), w(outs...);
	}
	inline void w(const char *p) {
		while (*p) {
			putchar(*p++);
		}
	}
}
#undef getchar
#undef putchar
using namespace FX;
#endif
using namespace std;
ll n, q, la, c, cnt[6];
string s;
vector<ll>v;

int main() {
	r(n, q);
	cin >> s;
	s = "0" + s + "0";
	for (ll i = 1; i < s.size(); i++) {
		n -= (s[i] ^ 48);
		if (s[i] == s[i - 1]) {
			c++;
			s[i - 1] = '0';
		} else {
			if ((s[i - 1] ^ 48) && c > 1) {
				cnt[2] += c;
				s[i - 1] = '0';
			}
			c = 1;
		}
	}
	for (ll i = 0; i < s.size(); i++) {
		if (s[i] ^ 48) {
			v.push_back(i);
		}
	}
	if (n != s.size() - 2) {
		if (v.size()) {
			c = 1;
			for (ll i = 1; i < v.size(); i++) {
				if (v[i] == v[i - 1] + 2) {
					c++;
				} else {
					cnt[1] += (c >> 1);
					cnt[0] += (c & 1);
					c = 1;
				}
			}
			cnt[1] += (c >> 1);
			cnt[0] += (c & 1);
		}
		while (q--) {
			ll x;
			r(x);
			x = min(x, n);
			if (cnt[1] >= x) {
				w(x * 3 + cnt[2]);
			} else if (cnt[1] + cnt[0] >= x) {
				w(cnt[1] * 3 + (x - cnt[1]) * 2 + cnt[2]);
			} else {
				w(cnt[1] * 3 + cnt[0] * 2 + cnt[2] + x - cnt[1] - cnt[0]);
			}
		}
	} else {
		while (q--) {
			ll x;
			r(x);
			x = min(x, n);
			if (x > 1) {
				w(x);
			} else {
				w(0);
			}
		}
	}
	return 0;
}