题解：P14258 好感（favor）

MhxMa · 2025-10-22 00:13:44 · 题解

话说 J 组第二题真的有这么难吗？我昨晚做梦都在想这道题。

（以下样例假设全部需要正面朝上，实际需要考虑两种情况）

不难发现，要使得移动距离最小，也就是要使每一个翻转的浮板所处位置最小。那么就可以先移动靠前的，例如：

但是如果用这种方法推下面这种情况，答案并不最优：

实际还可以：

由此可见，要使移动距离最小，就应该让所有要翻转的浮板尽可能的靠前。就可以先移动距离大的，由此推动前面的浮板前进，缩小前面浮板移动的距离。

但是如果用这种方法推下面这种情况，答案依旧并不最优：

实际还可以：

由此可见，如果此时要移动最后面的浮板，位置为 1 的浮板是反面朝上（1），那么移动这个最后面的浮板以后这个位置为 1 的浮板会被推到原来最后面浮板的位置，移动的距离大大增加。由此可以想到，当要移动最后面的浮板时，位置为 1 的浮板是反面朝上，那么先移动位置为 1 的浮板，再移动最后面的浮板。

用一个双端对列维护每一个反面朝上的浮板的位置，不难发现，该双端队列呈递增排列。对于一个没有被翻过的浮板，它现在的位置应该在原位置的基础上减去已经翻转的浮板数。若对头浮板的位置为 1，翻转该浮板，即去掉对头，距离增加 1。

使全部正面朝上记录完了，用同样的方法计算反面朝上，两者取最小即可。

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