粉碎题解

· · 题解

验题人题解。

分析

考虑贪心。

对于每次加进来的牌的点数，可以用一个数组记录下他的匹配情况，设 b_i 表示点数为 i 的牌还有多少张未匹配，注意到点数相同的牌两两匹配，并且每当存在 2 张相同的牌时，这 2 张牌一定会被粉碎掉。所以在正常情况下，b_i 的值为 0 或者 1。

对于每个加进来的点数为 A_i，若 b_{A_i} 不为 0，则代表可以有牌与这张牌匹配，那么匹配就可以有两种作用，下面分类讨论。

第一种作用：这张牌与另一张点数相同的牌一个在排队最左边，一个在最右边，显然这是容易做到的，那么这样就可以消掉 i 张牌。

第二种作用：可以特意将这两张牌夹着某张编号为 j 的牌（前提是 j<i 且 A_j\ne A_i，以及 j 没被匹配过，这是显然的），那么这样有什么用呢？这个匹配方式使用或不使用，代表着在以后得时刻点数为 A_j 的牌是否有未匹配的，那么既然可以保证 b_{A_j} 为我想要的值，并且 b_{A_j} 不为 0 时才是有用的，那么不妨直接设 b_{A_j} 为无穷大（这是因为对于新加入的点数 x，若 b_x 不为 0 则按照一开始所提及的匹配情况，程序会令 b_x 减一）。

然后就是，多测不清空，爆龄两行泪。

Code

#include <bits/stdc++.h>
using namespace std;
int a[500005], b[500005], p[500005], gan[500005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int ans = 0;
        int k = 0;
        for (int i = 1; i <= n; i++) {
            if (b[a[i]]) {
                ans = i;
                p[i] = 1;//匹配过
                for (int j = i - 1; j >= 1; j--) {
                    if (gan[j])
                        break;
                    gan[j] = 1;
                    if (!p[j] && a[j] != a[i])
                        b[a[j]] = 1000000000;
                }
                b[a[i]]--;
            } else
                b[a[i]]++;
        }
        for (int i = 1; i <= n; i++)
            b[a[i]] = p[i] = gan[i] = 0;
        cout << ans << '\n';
    }
    return 0;
}

可以发现，这份代码里用了一个“前缀优化”，就是由于每次修改是要修改一个前缀，而以前被修改过的地方就无需再进行修改了，这样就可以保证每个位置最多只会被修改一次，复杂度是 O(n) 的。

其实，这个优化还有一个精到之处，由于对于每次可以匹配、发挥作用的位置 i，它可以影响前 i-1 个位置，那么对于另一个可以匹配的位置 j(j>i)，它是否可以影响前 (i-1) 个位置呢？答案是不能，因为可以看做前 i-1 个位置是 i 所占据的地盘，那么在前 j-1 个位置中没被占据的位置才是属于 j 的。所以这个优化也保证了正确性。