题目描述

1≤n≤50000

---

题目分析

一个显然的性质，假设有 i 局是使用第一个规则，那么这一部分一定用掉前i大的牌。 贪心也是十分显然的，前半段中，一张对方的牌必须由己方中能打掉这张牌的数值最小的牌来匹配。后半段类似。 由于前后两部分求解是互不影响的，我们考虑使用前缀和后缀的方式来分别处理两部分。 由于是排列，所以我们可以使用线段树维护每一个数值区间内未匹配牌数（己方）和未被匹配牌数（对方）。这个简单讨论一下就可以合并。那么赢的局数就是总局数减去未匹配数。 前半部分位置 i 我们每次加入对方第i张牌以及己方第 i 大的牌，线段树维护一下答案。后半部分的话我们先将排列翻转，就可以将小的牌打大的牌变为和前半部分一样的大打小，使用相同方法维护。 最后扫一遍分割位置，前缀后缀相加更新答案。 时间复杂度O(nlog2n)。 原题貌似是某USACO金组题。

---

代码实现

#include <iostream> #include <cstring> #include <cstdio> #include <cctype> using namespace std; int read() { int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar(); while (isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f; } const int N=50050; const int A=N<<1; const int S=A<<2; struct segment_tree { int L[S],R[S],W[S]; void update(int x) { L[x]=L[x<<1],R[x]=R[x<<1|1],W[x]=W[x<<1]+W[x<<1|1]+min(R[x<<1],L[x<<1|1]); if (R[x<<1]<=L[x<<1|1]) L[x]+=L[x<<1|1]-R[x<<1]; else R[x]+=R[x<<1]-L[x<<1|1]; } void modify(int x,int y,int l,int r,bool tp) { if (l==r) { if (tp) L[x]=1,R[x]=W[x]=0; else R[x]=1,L[x]=W[x]=0; return; } int mid=l+r>>1; if (y<=mid) modify(x<<1,y,l,mid,tp); else modify(x<<1|1,y,mid+1,r,tp); update(x); } }t; int card[N],cme[N],pre[N],suf[N]; bool exist[A]; int n,a,ans; int main() { freopen("cardgame.in","r",stdin),freopen("cardgame.out","w",stdout); n=read(),a=n<<1; for (int i=1;i<=n;i++) exist[card[i]=read()]=1; for (int i=1;i<=a;i++) if (!exist[i]) cme[++cme[0]]=i; for (int i=1;i<=n;i++) { t.modify(1,card[i],1,a,0),t.modify(1,cme[n-i+1],1,a,1); pre[i]=t.W[1]; } for (int i=1;i<=n;i++) card[i]=a-card[i]+1,cme[i]=a-cme[i]+1; memset(t.L,0,sizeof t.L),memset(t.R,0,sizeof t.R),memset(t.W,0,sizeof t.W); for (int i=n;i>=1;i--) { t.modify(1,card[i],1,a,0),t.modify(1,cme[n-i+1],1,a,1); suf[i]=t.W[1]; } ans=0; for (int i=0;i<=n;i++) ans=max(ans,pre[i]+suf[i+1]); printf("%d\n",ans); fclose(stdin),fclose(stdout); return 0; }