月赛B题求调,思路应该是跟题解一样
  • 板块P6851 onu
  • 楼主XLao
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/10/7 10:29
  • 上次更新2023/11/5 11:44:18
查看原帖
月赛B题求调,思路应该是跟题解一样
83353
XLao楼主2020/10/7 10:29
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+1;
int n,m,h[N],ans[N];
int total_a[N],total_b[N];
ll c,v;

struct data
{
	int col,num,id;
}a[N],b[N];
bool cmp(data x,data y)
{
	if(x.col==y.col)
		return x.num>y.num;
	else
		return x.col<y.col;
}//按花色从小到大,点数从大到小排序两人的牌 

int main()
{
	scanf("%d%d%lld%lld",&n,&m,&c,&v);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].col,&a[i].num);
		a[i].id=i; total_a[a[i].col]++;
	}//小D的牌 
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
		if(a[i].col!=a[i-1].col)
		{
			h[a[i].col]=i;
		}//当前颜色在排序后数组中的开始位置 
	for(int i=1;i<=m;i++)
	{
		ans[i]=-1;
		scanf("%d%d",&b[i].col,&b[i].num);
		b[i].id=i; total_b[b[i].col]++;
	}//小C 
	sort(b+1,b+n+1,cmp);
	
	for(int i=1;i<=m;i++)//和标程不同的是这里我以小C的牌判输赢 
	{
		int color=b[i].col,now=h[color];
		if(a[now].num>=b[i].num && total_a[color])
		{
			ans[b[i].id]=a[now].id;
			v+=c+a[now].num;
			
			h[color]++;
			total_a[color]--;
			total_b[color]--;
		}
	}//能赢的就用最大的赢掉 
	
	for(int i=1;i<=m;i++)
	{
		if(b[i].col!=b[i-1].col)
		{
			int color=b[i].col,f=0;
			v-=total_b[color]*c;
			while(total_a[color] && total_b[color])
			{
				f=1;
				ans[b[i].id]=a[h[color]].id;
				v+=a[h[color]].num;
				
				h[color]++;  i++;
				total_a[color]--;
				total_b[color]--;
			}
			i-=f;
		}
	}//剩下输的 
	printf("%lld\n",v);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
2020/10/7 10:29
加载中...