P14258 好感（favor）题解

sunqihuan · 2025-10-22 19:53:26 · 题解

很好玩的贪心题。

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

接下来考虑移动产生的贡献抵消。设一共有 m 个反面滑板，对于第 i 个反面滑板，前面有 i-1 个，会产生 i-1 的距离抵消。不过如果滑板的编号减一大小于 m-i，那么这个滑板没办法移动那么多，最好的情况就是移动到第一个然后直接反面。取两者的最小值即可。

代码：

#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;
}