题解：P14258 好感（favor）

大概上位黄~下位绿。
我们讨论全部变成 0 总和最小为多少，全部变成 1 同理。
由题意得对第

i

个浮板进行操作所需代价为

i

。
显然的结论是不要操作已经是 0 的浮板。
如果第一个浮板为 1，如果不优先操作它它会被移到后面，立刻操作它显然是不劣的。
其他的情况，我们应操作最右边的反面浮板，这样可以使其他的浮板往前移，最终结果一定不劣。
对于每一个反面浮板

i

，操作一次它右边的反面浮板它就会往前 1 个距离，所以第

i

个浮板会在它右边浮板的操作中被移到第

i-\sum_{i<k}(k为反面)

的位置，而此时轮到它了，所以代价为

i-\sum_{i<k}(k为反面)

。
用双指针维护即可。记录当前最左边的反面浮板位置为

i

，当前最右边的反面浮板位置为

j

，已经翻的浮板数为

cnt

，则代价为

j-cnt

，如果

i=c

，则

i

到了位置 1，代价自增一。

CPP

// Problem: P14258 好感（favor）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14258
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Created Time: 2025-10-23 18:56:23
// Author: hjqhs
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
typedef long long ll;
typedef unsigned long long ull;
const int N = 1000005;
const int INF = 0x3f3f3f3f;
void solve() {
	int n; cin >> n;
	string s; cin >> s; s = ' ' + s;
	vector<int> a(n + 1), b(n + 1);
	int m1 = 0, res1 = 0 , cnt1 = 0;
	rep(i, 1, n) if(s[i] == '0') a[++ m1] = i;
	for(int i = 1, j = m1; i <= j; ) {
		res1 += (a[j] - cnt1), ++ cnt1, -- j;
		if(i <= j && a[i] == cnt1) ++ res1,++ i; 
	}
	int m2 = 0, res2 = 0, cnt2 = 0;
	rep(i, 1, n) if(s[i] == '1') b[++ m2] = i;
	for(int i = 1, j = m2; i <= j; ) {
		res2 += (b[j] - cnt2), ++ cnt2, -- j;
		if(i <= j && b[i] == cnt2) ++ res2, ++ i;
	}
	cout << min(res1, res2) << '\n';
	return;
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T;
	while(T --) solve();
	return 0;
}

题解：P14258 好感（favor）

文章操作

相关推荐

评论

题解：P14258 好感（favor）