P14258 好感（favor）题解

很好玩的贪心题。

首先肯定是分成全部变成正面和反面的情况讨论，这里以正面为例。显然每一个滑板如果是反面都要翻面，距离就是滑板的编号。所以最大的滑板距离就是所有反面的编号和。

接下来考虑移动产生的贡献抵消。设一共有

m

个反面滑板，对于第

i

个反面滑板，前面有

i-1

个，会产生

i-1

的距离抵消。不过如果滑板的编号减一大小于

m-i

，那么这个滑板没办法移动那么多，最好的情况就是移动到第一个然后直接反面。取两者的最小值即可。

代码：

CPP

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 5;

char b[N];
int pos[N], n;

int solve(char t)
{
	int m = 0, sum = 0;
	for(int i = 1; i <= n; i ++ ) 
		if(b[i] != t) pos[ ++ m] = i, sum += i;
	if(m == 0) return 0;
	for(int j = 1; j <= m; j ++ ) sum -= min(pos[j] - 1, m - j);
	return sum;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T -- )
	{
		cin >> n >> (b + 1);
		cout << min(solve('0'), solve('1')) << "\n";
	}
	return 0;
}

P14258 好感（favor）题解

文章操作

相关推荐

评论

P14258 好感（favor）题解