题意：
有 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 + 5; int A[N]; int dp[N][3]; int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); int n = a + b + c; for(int i = 1; i <= a; i++) { int x; scanf("%d", &x); A[x] = 0; } for(int i = 1; i <= b; i++) { int x; scanf("%d", &x); A[x] = 1; } for(int i = 1; i <= c; i++) { int x; scanf("%d", &x); A[x] = 2; } for(int i = 1; i <= n; i++) { dp[i][0] = dp[i - 1][0] + (A[i] != 0 ? 1 : 0); dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + (A[i] != 1 ? 1 : 0); dp[i][2] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])) + (A[i] != 2 ? 1 : 0); } printf("%d ", min(dp[n][0], min(dp[n][1], dp[n][2]))); return 0; }
官方解， 思维 + 贪心。
我们假设三个人的数编号为 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 + 5; int pos[N]; int cntR[5]; int cntL[5]; int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); int n = a + b + c; for(int i = 1; i <= a; i++) { int x; scanf("%d", &x); pos[x] = 1; } for(int i = 1; i <= b; i++) { int x; scanf("%d", &x); pos[x] = 2; } for(int i = 1; i <= c; i++) { int x; scanf("%d", &x); pos[x] = 3; } for(int i = 1; i <= n; i++) { cntR[pos[i]]++; } /// 整段都是 3 的。 int ans = cntR[1] + cntR[2]; int ma = 0; for(int i = 1; i <= n; i++) { cntL[pos[i]]++; cntR[pos[i]]--; ma = max(ma, cntL[1] - cntL[2]); int tmp = cntR[1] + cntR[2] + cntL[3] + cntL[1] - ma; ans = min(ans, tmp); } printf("%d ", ans); return 0; }