专栏文章

题解：P14258 好感（favor）

MMhxMa
P14258题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjedx9
此快照首次捕获于
2025/12/02 03:23
3 个月前
此快照最后确认于
2025/12/02 03:23
3 个月前
查看原文
话说 J 组第二题真的有这么难吗？我昨晚做梦都在想这道题。
（以下样例假设全部需要正面朝上，实际需要考虑两种情况）
不难发现，要使得移动距离最小，也就是要使每一个翻转的浮板所处位置最小。那么就可以先移动靠前的，例如：
110110 → 010010 → 000000，总移动距离为 1+2=31+2=3
但是如果用这种方法推下面这种情况，答案并不最优：
011011 → 001001 → 000000，总移动距离为 2+3=52+3=5
实际还可以：
011011 → 100100 → 000000，总移动距离为 3+1=43+1=4
由此可见，要使移动距离最小，就应该让所有要翻转的浮板尽可能的靠前。就可以先移动距离大的，由此推动前面的浮板前进，缩小前面浮板移动的距离。
但是如果用这种方法推下面这种情况，答案依旧并不最优：
1011010110 → 0101001010 → 1000010000 → 0000000000，总移动距离为 4+4+1=94+4+1=9
实际还可以：
1011010110 → 0011000110 → 0100001000 → 0000000000，总移动距离为 1+4+2=71+4+2=7
由此可见，如果此时要移动最后面的浮板，位置为 11 的浮板是反面朝上（11），那么移动这个最后面的浮板以后这个位置为 11 的浮板会被推到原来最后面浮板的位置，移动的距离大大增加。由此可以想到，当要移动最后面的浮板时，位置为 11 的浮板是反面朝上，那么先移动位置为 11 的浮板，再移动最后面的浮板。
用一个双端对列维护每一个反面朝上的浮板的位置，不难发现，该双端队列呈递增排列。对于一个没有被翻过的浮板，它现在的位置应该在原位置的基础上减去已经翻转的浮板数。若对头浮板的位置为 11，翻转该浮板，即去掉对头，距离增加 11。
使全部正面朝上记录完了，用同样的方法计算反面朝上，两者取最小即可。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 5;

int T;
int n;
deque<int> q;
int ans1, ans2;
string s;
int cnt;

signed main() {
//	freopen("favor3.in", "r", stdin);
	scanf("%lld", &T);
	while (T--) {
		ans1 = ans2 = 0;

		scanf("%lld", &n);
		cin >> s;

		for (int i = 1; i <= n; ++i) {
			char c = s[i - 1];
			if (c == '1') {
				q.push_back(i);
			}
		}

		cnt = 0;
		while (!q.empty()) {
			ans1 += q.back() - cnt;
			++cnt;
			q.pop_back();
			if (!q.empty() && q.front() == cnt) {
				++ans1;
				q.pop_front();
			}
		}

// ------------
		for (int i = 1; i <= n; ++i) {
			char c = s[i - 1];
			if (c == '0') {
				q.push_back(i);
			}
		}
		cnt = 0;
		while (!q.empty()) {
			ans2 += q.back() - cnt;
			++cnt;
			q.pop_back();
			if (!q.empty() && q.front() == cnt) {
				++ans2;
				q.pop_front();
			}
		}

		printf("%lld\n", min(ans1, ans2));
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...