洛谷 P6851 【onu】贪心-白红宇

洛谷 P6851 【onu】贪心

阅读量：428 次

发布时间：2019-03-06

本文共 1815 字，大约阅读时间需要 6 分钟。

题目描述

分析

因为小 $D$ 打出的牌与小 $C$ 打出的牌花色必须相同，所以我们需要按照花色分类讨论

对于某一种花色

如果小 $C$ 没有这种花色的牌但是小 $D$ 有，那么小 $D$ 的牌一定打不出去，直接 $continue$ 掉

如果小 $C$ 有这种花色的牌，那么对于小 $D$ 来说，他肯定想让他赢的次数尽可能多

这其实就是一个田忌赛马的问题

我们把小 $C$ 和小 $D$ 的牌按照点数从大到小排序

对于小 $D$ 的每一张牌，我们在小 $C$ 小于等于这张牌点数的牌里选择点数最大的那一张与其配对

因为消耗一个点数大的牌肯定更优，这样可以为之后的牌创造更多的获胜机会

因为小 $D$ 的牌的点数是单调递减的，所以选出的牌的点数也一定是单调递减的

因此，我们可以用一个指针维护

这样到最后小 $D$ 的牌要么都打光，要么剩下一些

对于剩下的牌，我们随便配对就可以了，因为打出去肯定比不打出去更优

在匹配的过程中如果小 $C$ 的牌不够用，那么就停止匹配

如果小 $D$ 的牌打光后小 $C$ 还剩下牌，那么小 $D$ 只能选择弃权

代码

#include
   
    #include
    
     #include
     
      #include
      
       #define rg registerstruct asd{	int id,val;	asd(){}	asd(int aa,int bb){ id=aa,val=bb; }};bool cmp(asd aa,asd bb){	return aa.val>bb.val;}const int maxn=1e5+5;std::vector
       
         gd[maxn],gc[maxn];int ans[maxn],n,m,maxid;long long c,v;bool vis[maxn];void solve(int id){	if(gc[id].size()==0) return;	rg int head=0,js=0;	for(rg int i=0;i
        
         =gc[id].size()) break; while(1){ if(gc[id][head].val>cs) head++; if(head>=gc[id].size()) break; if(gc[id][head].val<=cs){ ans[gc[id][head].id]=gd[id][i].id; vis[gc[id][head].id]=1; v=v+c+gd[id][i].val; head++,js++; break; } } } for(rg int i=0;i
         
          =gd[id].size()){ ans[now]=-1; vis[now]=1; v=v-c; } else { ans[now]=gd[id][js].id; v=v-c+gd[id][js].val; vis[now]=1; js++; } }}int main(){ scanf("%d%d%lld%lld",&n,&m,&c,&v); rg int aa,bb; for(rg int i=1;i<=n;i++){ scanf("%d%d",&aa,&bb); gd[aa].push_back(asd(i,bb)); maxid=std::max(maxid,aa); } for(rg int i=1;i<=m;i++){ scanf("%d%d",&aa,&bb); gc[aa].push_back(asd(i,bb)); maxid=std::max(maxid,aa); } for(rg int i=1;i<=maxid;i++){ std::sort(gd[i].begin(),gd[i].end(),cmp); std::sort(gc[i].begin(),gc[i].end(),cmp); } for(rg int i=1;i<=maxid;i++) solve(i); printf("%lld\n",v); for(rg int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0;}