题解——P14258 好感（favor）

· · 题解

题目传送门

题目大意

给你一个 n 个浮板，小 S 每次操作可以用 i 的代价把第 i 个浮板翻面，同时所有 j\le i 的浮板会移动到 j-1 的位置，然后小 Y 会把 0 号位上的浮板不翻面地挪到 i 号位上，求把所有浮板变成同一面朝上的最小代价。

思路

本题考察贪心。

先只考虑全部翻成反面朝上的情况。

因为每次操作都会且仅会使一个浮板翻面，所以把原来就是反面的浮板翻掉肯定不是最优的。同时，如果对第 i 个位置的浮板操作一次，那么满足 j<i 的所有浮板都会往前移，当再去翻前面这些些浮板的时候，所需的代价就会减一。所以要优先把后面的浮板翻掉，使可以减少的代价最多。

从后往前贪心，若第 i 个位置是 0 ，那直接忽略。否则要把当前位置变成 1 。这时，先确保第 1 个浮板是反面（不然就对它操作一次，把它变成反面），然后对第 i 个浮板操作一次，使之变成反面朝上。

举个栗子，样例里的 1011100 会经历如下过程

1011100->0011100->0110000->1000000->0000000

ans=1+5+3+1=10

全部翻成正面朝上的情况同理，然后把算出来的两个答案取 \min 即可。

Code

如果暴力模拟这个过程，那么 T 飞了，时间复杂度是 O(n^2) 的，期望只有 60 pts 。

但是我们可以使用嘿科技 deque 来模拟，这样把时间复杂度降到了 O(n) ，然后就可以愉快地 AC 这道题了。

最后，十年 OI 一场空，不开 见祖宗！

#include <bits/stdc++.h>

using namespace std;
const int N = 1145140;

#define endl '\n'
#define int long long //防止溢出

deque <char> q; //STL niubi!!!
string s;
int n;

void solve() {
    cin >> n;
    cin >> s;
    for (int i = 0; i < n; i++) q.push_back(s[i]);
    int ans1 = 0, ans2 = 0;

    while (!q.empty()) {
        if (q.back() == '1') {
            if (q.size() == 1) {
                ans1++;
                q.pop_back();
                break;
            } //特判一下，防止RE
            ans1 += q.size();
            if (q.front() == '1') ans1++;//确保第一个浮板是反面
            q.pop_front();
            q.pop_back();
        } else q.pop_back();
    } //全部翻成反面朝上

    for (int i = 0; i < n; i++) q.push_back(s[i]);

    while (!q.empty()) {
        if (q.back() == '0') {
            if (q.size() == 1) {
                ans2++;
                q.pop_back();
                break;
            } //特判一下，防止RE
            ans2 += q.size();
            if (q.front() == '0') ans2++;//确保第一个浮板是正面
            q.pop_front();
            q.pop_back();
        } else q.pop_back();
    }//全部翻成正面朝上

    cout << min(ans1, ans2);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
        cout << endl;
    }//多测
    return 0;
}