JZOJ4686 卡牌游戏线段树维护贪心策略

题目大意

有两个人在玩这样的一个游戏：现在有 2N 张牌，牌的大小为 1 到2N，每个人都从中拿 N 张牌来进行N轮比大小。现在你已经知道第二个人的出牌顺序，你要帮第一个人赢得经量多（你可以决定他的出牌顺序）。比大小的规则是这样的：一开始是谁牌上的数字大谁就赢。但是当游戏进行了若干轮后，你可以改变游戏规则，变为谁的牌小谁赢（只能修改一次！）。问最优策略下第一个人能赢多少轮。

N≤50000

解题思路

看到题目，一个显然的思想就是在转换规则前加入进行了k轮，那么这k轮出的牌肯定是前k大的。现在就是要维护前k张牌所能达到的最大贡献。（现在只讨论改变规则前的情况，改变规则后的可以用类似的方法去完成。）

那么我们贪心的去出牌。对于每张牌，我们最贪心的想法就是找到一张对手恰好小于它的牌来配对。然后让这两张牌配对，删除，重复上面的操作，直到不能配对。当我们处理完第一个人的前i张牌时对于第i张牌的维护就有写技巧了。

我们可以用线段树来维护，线段树的下标表示牌的大小，上面的每段区间维护三个值：当前的答案，第一个人剩的牌，第二个人剩的牌。合并两个区间时只需考虑右区间中第一个人的牌有多少，左区间中第二个人的牌有多少，取个min就是区间合并贡献的答案，然后再合并牌的信息就可以了。时间复杂度是O(NlogN)

程序

//YxuanwKeith #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 1e5 + 5; struct Tree { int A, B, Get; } Tr[MAXN * 8]; bool Flag[MAXN * 2]; int N, A[MAXN], B[MAXN], F[MAXN], G[MAXN]; void Insert(int Now, int l, int r, int Side) { if (l == r) { Tr[Now].A ++; return; } int Mid = (l + r) >> 1; if (Side <= Mid) Insert(Now * 2, l, Mid, Side); else Insert(Now * 2 + 1, Mid + 1, r, Side); Tr[Now].A = Tr[Now * 2].A + Tr[Now * 2 + 1].A; } void Modify(int Now, int l, int r, int Side) { if (l == r) { Tr[Now].B ++; return; } int Mid = (l + r) >> 1; if (Side <= Mid) Modify(Now * 2, l, Mid, Side); else Modify(Now * 2 + 1, Mid + 1, r, Side); int Get = min(Tr[Now * 2].B, Tr[Now * 2 + 1].A); Tr[Now].A = Tr[Now * 2].A + Tr[Now * 2 + 1].A - Get; Tr[Now].B = Tr[Now * 2].B + Tr[Now * 2 + 1].B - Get; Tr[Now].Get = Tr[Now * 2].Get + Tr[Now * 2 + 1].Get + Get; } int main() { scanf("%d", &N); for (int i = 1; i <= N; i ++) { scanf("%d", &A[i]); Flag[A[i]] = 1; } for (int i = 1; i <= 2 * N; i ++) if (!Flag[i]) B[++ B[0]] = i; for (int i = N; i; i --) Insert(1, 1, 2 * N, B[i]); for (int i = 1; i <= N; i ++) { Modify(1, 1, 2 * N, A[i]); F[i] = Tr[1].Get; } memset(Tr, 0, sizeof Tr); for (int i = N; i; i --) Insert(1, 1, 2 * N, 2 * N - B[i] + 1); for (int i = N; i; i --) { Modify(1, 1, 2 * N, 2 * N - A[i] + 1); G[i] = Tr[1].Get; } int Ans = 0; for (int i = 0; i <= N; i ++) Ans = max(Ans, F[i] + G[i + 1]); printf("%d\n", Ans); }