E. The Contest （简单DP || 思维 + 贪心）

传送门

题意：

　　有 n 个数（1 ~ n）分给了三个人 a, b, c；其中 a 有 k1 个， b 有 k2 个， c 有 k3 个。

　　现在问最少需要多少操作，使得 a 中所有数是 1 ~ n 的一个前缀；

　　c 中所有数是 1 ~ n 的一个后缀。剩下的都在 b 手上。

　　每次操作可以让一个人手上的一个数给另一个人。

解：简单 DP ；显然就是问你把 1 ~ n 分成三段的最少花费。

　　你把第一个人最初拥有的数，所在的桶定义为 0；

　　第二个人的为1，第三个人的为2。

　　然后你就可以 DP 了；

　　dp[ i ][ 0 ] 就代表，你的第一个人取 1 ~ i 的花费。

　　dp[ i ][ 1 ] 就表示，第一个人拿了 1 ~ i 的前缀 1 ~ pos 部分，第二个人拿了，剩下的 pos ~ i 部分的最少花费。

　　dp[ i ][ 2 ] 类似。看代码的式子应该就懂了。

#include <bits/stdc++.h>

#define LL long long

#define rep(i, j, k) for(int i = j; i <= k; i++)

#define dep(i, j, k) for(int i = k; i >= j; i--)

#define INF 0x3f3f3f3f

#define inf 0x3f3f3f3f3f3f3f3f

#define mem(i, j) memset(i, j, sizeof(i))

#define pb push_back

using namespace std;

const int N = 2e5 + ;

int A[N];

int dp[N][];

int main() {

    int a, b, c; scanf("%d %d %d", &a, &b, &c);

    int n = a + b + c;

    for(int i = ; i <= a; i++) {

        int x; scanf("%d", &x); A[x] = ;

    }

    for(int i = ; i <= b; i++) {

        int x; scanf("%d", &x); A[x] = ;

    }

    for(int i = ; i <= c; i++) {

        int x; scanf("%d", &x); A[x] = ;

    }

    for(int i = ; i <= n; i++) {

        dp[i][] = dp[i - ][] + (A[i] !=  ?  : );

        dp[i][] = min(dp[i - ][], dp[i - ][]) + (A[i] !=  ?  : );

        dp[i][] = min(dp[i - ][], min(dp[i - ][], dp[i - ][])) + (A[i] !=  ?  : );

    }

    printf("%d\n", min(dp[n][], min(dp[n][], dp[n][])));

    return ;

}

官方解，思维 + 贪心。

　　我们假设三个人的数编号为 1 2 3

　　首先，假设我们定了 L， R。就是说， 1 ~ L 这一段是第一个人的， L ~ R 这一段是第二个人的。

　　R ~ n 这一段是第三个人的。那么，你若确定了 L， R。那么你的答案，就是固定的。

　　我们假设 cnt[ L ][ i ] 表示 1 ~ L 这一段是 i 个人的数的个数。

　　我们假设 1 ~ L 这一段为 L， L ~ R 这一段为 M 。 R ~ n 这一段为 R

　　那么答案就是 cnt[ L ][ 2 ] + cnt[ L ][ 3 ] + cnt[ M ][ 1 ] + cnt[ M ][ 3 ] + cnt[ R ][ 1] + cnt[ R ][ 2 ]；

　　对吧。那现在，要是我们确定了 R 这个点。然后， L 应该在什么位置才是最优的呢。

　　假设R 确定了。那么 cnt[ L ][ 3 ] + cnt[ M ][ 3 ] , cnt[ R ][ 1 ] ， cnt[ R ][ 2 ] 全都确定了嘛。

　　那么还差 cnt[ L ][ 2 ] 和， cnt[ M ][ 1 ] 没有确定嘛。那你想要这两个值尽可能的小嘛。

　　那么就是你希望， 1 ~ L 这一段中 2 的数的个数尽可能少， L ~ R 这一段中 1 的数的个数尽可能少。

　　那也可以说成，你 1 ~ L 这一段中， 1 的个数尽可能的多， 2的个数尽可能的少嘛。

　　因为你 1 ~ L 中 1 的个数尽可能多的话呢，你 L ~ R 这一段中 1 的个数就自然小了嘛。

　　那不就是 cnt[ L ][ 1 ] - cnt[ L ][ 2 ] 最大的时候的位置，就是 L 的位置吗。

　　那么，我们枚举 R，再维护一个 cnt[ L ][ 1 ] - cnt[ L ][ 2 ] 的最大值。

　　就可以确定 R 在这个点时的最小答案了。

　　我们假设 cnt[ L ][ 1 ] - cnt[ L ][ 2 ] 的最大值为 ma

　　那么我们现在让 R ~ n 这一段为 R， 1 ~ R 这一段为 LL 。

　　那么答案就是 cnt[ R ][ 1 ] + cnt[ R ][ 2 ] + cnt[ LL ][ 3 ] + cnt[ LL ][ 1 ] - ma；

　　就是答案了。 cnt[ LL ][ 1 ] - ma。这一段代表的东西就是。

　　你 ma 这个值是在最优的 L 处取得的嘛。

　　那就是， 1 ~ R 这一段的所有的 1 减去，你 1 ~ L 这一段的不需要动的1嘛。

　　那得到的就是 L ~ R 这一段 1 的个数。

　　再加上你 1 ~ L 这一段的 2 的个数嘛。那就刚好是前面的 cnt[ L ][ 2 ] + cnt[ M ][ 1 ]。

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const int N = 2e5 + ;

int pos[N];

int cntR[];

int cntL[];

int main() {

    int a, b, c; scanf("%d %d %d", &a, &b, &c);

    int n = a + b + c;

    for(int i = ; i <= a; i++) {

        int x; scanf("%d", &x);

        pos[x] = ;

    }

    for(int i = ; i <= b; i++) {

        int x; scanf("%d", &x);

        pos[x] = ;

    }

    for(int i = ; i <= c; i++) {

        int x; scanf("%d", &x);

        pos[x] = ;

    }

    for(int i = ; i <= n; i++) {

        cntR[pos[i]]++;

    }

    /// 整段都是 3 的。

    int ans = cntR[] + cntR[];

    int ma = ;

    for(int i = ; i <= n; i++) {

        cntL[pos[i]]++;

        cntR[pos[i]]--;

        ma = max(ma, cntL[] - cntL[]);

        int tmp = cntR[] + cntR[] + cntL[] + cntL[] - ma;

        ans = min(ans, tmp);

    }

    printf("%d\n", ans);

    return ;

}

巴特西

E. The Contest （简单DP || 思维 + 贪心）

最新文章

热门文章

巴特西

E. The Contest （ 简单DP || 思维 + 贪心）

最新文章

热门文章

E. The Contest （简单DP || 思维 + 贪心）