THE CONTEST

阅读数: 次 2019-11-16

字数统计: 868字 | 阅读时长: 3分

题意
三个人，每个人有一些数字，组合起来是$1$~$n$，每个人可以给另一个人一个拥有的数字，问最小操作数，使得第一个人拥有$1$~$i$的数，第二个人拥有$i+1$~$j$的数，第三个人拥有$j+1$~$n$的数，即第一个人为前缀，第二个人为中间部分，第三个人为后缀。
注意：可以有一个或两个人最后不拥有数字。

分析
看到三个人操作，我们先看两个人操作时的情况：
假设到最后，第一个人拥有$1$~$i$，第二个人拥有$i+1$~$n$，那么最小操作数为第二个人$1$~$i$中中拥有的数字加上第一个人$i+1$~$n$中拥有的数字。我们可以采用前缀和，$cnt1[k]$表示第一个人前$k$个数中拥有的个数，$cnt2[k]$表示第二个人前$k$个数中拥有的个数,则表达式为：$$cnt2[i]+cnt1[n]-cnt1[i]$$受到启发我们看三个人操作时的情况：
假设到最后，第一个人拥有$1$~$i$，第二个人拥有$i+1$~$j$，第三个人拥有$j+1$~$n$，那么最小操作数为第二个人和第三个人$1$~$i$中拥有的个数加上第一个人和第三个人$i+1$~$j$中拥有的个数加上第一个人和第二个人$j+1$~$n$中拥有的个数。我们可以采用前缀和，$cnt1[k]$表示第一个人前$k$个数中拥有的个数，$cnt2[k]$表示第二个人前$k$个数中拥有的个数，$cnt3[k]$表示第三个人前$k$个数中拥有的个数则表达式为：$$cnt2[i]+cnt3[i]+cnt1[j]-cnt1[i]+cnt3[j]-cnt3[i]+cnt1[n]-cnt1[j]+cnt2[n]-cnt2[j]$$化简得到:$$cnt2[i]-cnt1[i]+cnt3[j]-cnt2[j]+cnt1[n]+cnt2[n]$$我们从$0$~$n$枚举$i$，接下来我们考虑$j$的取值，我们可以看到对于固定的$i$，只需要找到一个$j$使得该式子最小即可，那么我们可以设置一个后缀$minn[]$数组，$minn[i]$表示当$i\leq j\leq n$时，$cnt3[j]-cnt2[j]$最小的值，那么答案即为：$$cnt2[i]-cnt1[i]+minn[i]+cnt1[n]+cnt2[n]$$
代码

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define LL long long
using namespace std;
const int maxn = (ll) 2e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
int cnt1[maxn], cnt2[maxn], cnt3[maxn];
int minn[maxn];
vector<int> v1, v2, v3;

int main() {
    start;
    int k1, k2, k3;
    cin >> k1 >> k2 >> k3;
    v1.resize(k1 + 5);
    v2.resize(k2 + 5);
    v3.resize(k3 + 5);
    /*输入并标记*/
    for (int i = 1; i <= k1; ++i) {
        cin >> v1[i];
        ++cnt1[v1[i]];
    }
    for (int i = 1; i <= k2; ++i) {
        cin >> v2[i];
        ++cnt2[v2[i]];
    }
    for (int i = 1; i <= k3; ++i) {
        cin >> v3[i];
        ++cnt3[v3[i]];
    }
    int n = k1 + k2 + k3;
    for (int i = 1; i <= n; ++i) {//前缀和
        cnt1[i] = cnt1[i - 1] + cnt1[i];
        cnt2[i] = cnt2[i - 1] + cnt2[i];
        cnt3[i] = cnt3[i - 1] + cnt3[i];
    }
    /*如分析*/
    for (int i = 0; i <= n; ++i)
        minn[i] = cnt3[i] - cnt2[i];
    for (int i = n - 1; i >= 0; --i)
        minn[i] = min(minn[i + 1], minn[i]);
    int ans = inf;
    for (int i = 0; i <= n; ++i) {
        int t = cnt2[i] - cnt1[i] + minn[i] + cnt1[n] + cnt2[n];
        ans = min(ans, t);
    }
    cout << ans;
    return 0;
}

本场比赛$D$和$E$惨痛教训：玩后缀一定要注意边界！！！
若有问题可在评论区提出，谢谢。