【题意】
L最近喜欢上了一个卡片游戏，游戏规则是： 2 个人一共拿 2n 张卡片，编号 1..2n，每个人 n 张，然后进行 n 轮出牌，每轮 2 个 人都打一张牌，，点数大的玩家每次获 1分。 L可以预测到对方要打牌的顺序。 同时，L有一次机会选择了某个时间点，从那个时候开始，每回合点数少者获胜。 请你帮助 L获得最大的分数
我们用贪心来做
假设规则没有变的时候 对于对方打出的一张牌 L从他的牌里打出一张刚好比这张牌大的牌显然是最优的
假设规则变了的时候 对于对方打出的一张牌 L从他的牌里打出一张刚好比这张牌小的显示是最优的
似乎这个地方也有另一种贪心的方法 对于每一张牌 找一个最大的比他的牌也是可行的 因为这样在变规则后 可以使得剩下的牌更好得分
我们考虑如何实现
我们维护两个数组 front back，front[i]：没变规则时，1~i轮能得到的最大分数 back[i]：变了规则后，i~n轮能得到的最大分数
答案为max{front[i]+back[i+1]}
很多人都会提到说 可能一张牌在点数大的赢的时候被用了，后面改规则后也被用了，就被重复用了两次。
但是其实没有关系。如果一张牌a被用了两次，那么就说明手中有一张牌设为b没有被用过。若a>b，那么在点数小的赢那轮可以用b去替代a来赢得胜利；反之亦然。
最后 数组记得开100000 不然会炸成30分
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,cnt; int t[N],card[N],sx[N]; int front[N],back[N]; bool used[N]; int find_upper(int x) { int l=0,r=n; while(l<=r) { int m=(l+r)>>1; if(card[m]>x) r=m-1; else l=m+1; } return l; } int find_lower(int x) { int l=0,r=n; while(l<=r) { int m=(l+r)>>1; if(card[m]>x) r=m-1; else l=m+1; } return l-1; } int main() { freopen("cardgame.in","r",stdin); freopen("cardgame.out","w",stdout); memset(used,false,sizeof(used)); cin>>n; for(int i=1;i<=n;i++) { cin>>sx[i]; t[sx[i]]++; } for(int i=1;i<=2*n;i++) { if(!t[i]) card[++cnt]=i; } for(int i=1;i<=n;i++) { int pos=find_upper(sx[i]); while(used[pos]==true) pos++; if(pos>n) front[i]=front[i-1]; else { used[pos]=true; front[i]=front[i-1]+1; } } //for(int i=1;i<=n;i++) cout<<front[i]<<" "; memset(used,false,sizeof(used)); for(int i=n;i>=1;i--) { int pos=find_lower(sx[i]); while(used[pos]==true) pos--; if(pos<1) back[i]=back[i+1]; else { used[pos]=true; back[i]=back[i+1]+1; } } //for(int i=1;i<=n;i++) cout<<back[i]<<" "; int ans=0; for(int i=0;i<=n;i++) { ans=max(front[i]+back[i+1],ans); } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9734746.html
