洛谷 P6851 【onu】貪心

• 2020 年 10 月 11 日
• 筆記
• 貪心

題目描述

題目傳送門

分析

因為小 \(D\) 打出的牌與小 \(C\) 打出的牌花色必須相同，所以我們需要按照花色分類討論

對於某一種花色

如果小 \(C\) 沒有這種花色的牌但是小 \(D\) 有，那麼小 \(D\) 的牌一定打不出去，直接 \(continue\) 掉

如果小 \(C\) 有這種花色的牌，那麼對於小 \(D\) 來說，他肯定想讓他贏的次數儘可能多

這其實就是一個田忌賽馬的問題

我們把小 \(C\) 和小 \(D\) 的牌按照點數從大到小排序

對於小 \(D\) 的每一張牌，我們在小 \(C\) 小於等於這張牌點數的牌里選擇點數最大的那一張與其配對

因為消耗一個點數大的牌肯定更優，這樣可以為之後的牌創造更多的獲勝機會

因為小 \(D\) 的牌的點數是單調遞減的，所以選出的牌的點數也一定是單調遞減的

因此，我們可以用一個指針維護

這樣到最後小 \(D\) 的牌要麼都打光，要麼剩下一些

對於剩下的牌，我們隨便配對就可以了，因為打出去肯定比不打出去更優

在匹配的過程中如果小 \(C\) 的牌不夠用，那麼就停止匹配

如果小 \(D\) 的牌打光後小 \(C\) 還剩下牌，那麼小 \(D\) 只能選擇棄權

代碼

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#define rg register
struct 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<asd> 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<gd[id].size();i++){
		rg int cs=gd[id][i].val;
		if(head>=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<gc[id].size();i++){
		rg int now=gc[id][i].id;
		if(vis[now]) continue;
		if(js>=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;
}