P10168题解

· · 题解

题意

我们需要进行若干次操作，使得字符串 s 的顺序对数量最大。每次操作可以将 s 中相邻的两个值取反。

分析

由于 s 只包含 0 和 1，所以为了使顺序对数量最大，我们尽可能将 1 放在末尾，将 0 尽可能放在前面。可以发现，经过操作后，0 或 1 的数量会发生改变。所以，这也为我们后续的操作奠定了基础。

首先，我们将问题简化：我们可以让字符串 s 末尾有任意数量的 1，开头有任意数量的 0，那么我们该如何分配 1 和 0 的数量，使得顺序对数量最大呢？

相信大家都明白这个道理吧：在周长相等的正方形与长方形中，正方形面积总比长方形大。为什么？因为正方形的边长相等，也就是差值为 0。

转换为数学逻辑就是：x1\times x2 与 y1\times y2 相比（x1+x2=y1+y2，为了方便起见，设 x1\le x2,y1\le y2），若 x2-x1<y2-y1，则 x1\times x2>y1\times y2；反之同理。

举个例子：若 s 的长度为 5，则最优情况下 s 中有两个 0，三个 1，或者有三个 0，两个 1。

清楚这个问题后，再来考虑题目。我们要尽可能让 1 靠后，0 考前，且 1 的数量与 0 的数量相差小，则我们由字符串的末尾像中间枚举，若枚举到的字符为 0，则使用一次操作；同理，再由字符串的开头像中间枚举，若枚举到的字符为 1，则使用一次操作。

枚举 1 的情况时若枚举到的字符为 0，则使用一次操作，为什么这样可以保证字符串从中间到末尾都为 1 呢？假设该字符前一个字符为 0，则两全其美，这两个字符都变为了 1；若前一个字符为 1，则在操作之后，前一个字符变为 0，但是不用担心，因为在下一轮的枚举中前一个字符又会变为 1。

Code

#include <bits/stdc++.h>
using namespace std;
int ans, a[200005];

int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i = n - 1; i >= n / 2; i--) {
        if (s[i] == '0') {
            a[++ans] = i;
            s[i] = '1';
            if (s[i - 1] == '0')
                s[i - 1] = '1';
            else
                s[i - 1] = '0';
        }
    }
    for (int i = 0; i < n / 2; i++) {
        if (s[i] == '1') {
            a[++ans] = i + 1;
            s[i] = '0';
            if (s[i + 1] == '0')
                s[i + 1] = '1';
            else
                s[i + 1] = '0';
        }
    }
    long long o = 0;
    for (int i = 0; i < n; i++)
        if (s[i] == '1')
            o++;
    long long tmp = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0')
            tmp += o;
        else
            o--;
    }
    cout << tmp << endl << ans << endl;
    for (int i = 1; i <= ans; i++)
        cout << a[i] << " ";
}

打字不易，请管理大大通过吧！也请各位点个赞！

另外附上赛事记录