自动搬运

查看原文

来自洛谷，原作者为

	yangwenbin 这个家伙不懒，什么也没有留下

搬运于2025-08-24 22:24:35，当前版本为作者最后更新于2020-10-10 16:31:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 P6851 【onu】

P6851 onu

这道题是一道很典型的贪心的题目。

首先小 D 每一次出牌都会买等于自己牌面的糖果数

其次赢了还可以多拿到 c 个糖果 ， 输了就失去 c 个糖果。

所以要赢，同时要赢得大。

这里就很像田忌赛马了。用自己小的和别人大的比，用大的去赢别人。

但这多一个颜色，就在排序贪心是，优先颜色（从小到大），其次牌面（从大到小）

操作时，先赢后输，先把能赢得都赢了，再考虑怎么输：

inline void win()
{
	int i = 1,j = 1;
	for (; i <= n; ++i)
	{
		if (put[i]) continue;
		while (C[j].color < D[i].color && j <= m) ++j; // 调整颜色至两张牌颜色统一
		for (;j <= m && D[i].color == C[j].color; ++j)
		{
			if (vis[j]) continue;// 如果这张牌用过了就跳过
			if (D[i].num >= C[j].num) //能赢的最大的牌，赢掉这张，最大降低对方牌面大小
			{
				put[i] = vis[j] = true;
				sum += (D[i].num + each);
				ans[C[j].indax] = D[i].indax;
				break;
			}
		}
	}
	return ;
}

然后考虑输的情况，大大牌肯定是要出的，小牌可以不出，

如果，小 D 的牌少，就输出 -1 ，所以

inline void lose()
{
	int i = 1,j = 1;
	for (; i <= n; ++i)
	{
		if (put[i]) continue;
		while (C[j].color < D[i].color && j <= m) ++j;
		for (;j <= m && D[i].color == C[j].color; ++j)
		{
			if (vis[j]) continue;
			sum += (D[i].num - each);
			put[i] = vis[j] = true;
			ans[C[j].indax] = D[i].indax;
			break;
		}
	}
	for (int x = 1; x <= m; ++x)
	{
		if (vis[x]) continue;
		sum -= each;
	}
	return ;
}

code

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int SIZE = 1e5 + 50;

inline int read()
{
	int x = 0,f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		f = (ch == '-' ? -1 : 1);
		ch =  getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return f * x;
}

int n,m,each,sum;
int color[SIZE],ans[SIZE];
bool vis[SIZE],put[SIZE];
struct onu
{
 	int color,num,indax;
};
onu C[SIZE],D[SIZE];

inline bool cmp(onu a,onu b) 
{
	return (a.color == b.color ? (a.num == b.num ? a.indax < b.indax : a.num > b.num) : a.color < b.color);
}

inline void get()
{
	memset(ans,-1,sizeof(ans));
	n = read();m = read();each = read();sum = read();
	for (int i = 1; i <= n; ++i)
	{
		D[i].color = read();D[i].num = read();D[i].indax = i;
	}
	for (int i = 1; i <= m; ++i)
	{

		C[i].color = read();C[i].num = read();C[i].indax = i;
	}
	sort(C+1,C+1+m,cmp);sort(D+1,D+1+n,cmp);
}

inline void win()
{
	int i = 1,j = 1;
	for (; i <= n; ++i)
	{
		if (put[i]) continue;
		while (C[j].color < D[i].color && j <= m) ++j;
		for (;j <= m && D[i].color == C[j].color; ++j)
		{
			if (vis[j]) continue;
			if (D[i].num >= C[j].num)
			{
				put[i] = vis[j] = true;
				sum += (D[i].num + each);
				ans[C[j].indax] = D[i].indax;
				break;
			}
		}
	//	cout << D[i].indax << " " << D[i].num << " " << each << " " << sum << endl;
	}
	return ;
}

inline void lose()
{
	int i = 1,j = 1;
	for (; i <= n; ++i)
	{
		if (put[i]) continue;
		while (C[j].color < D[i].color && j <= m) ++j;
		for (;j <= m && D[i].color == C[j].color; ++j)
		{
			if (vis[j]) continue;
			sum += (D[i].num - each);
			put[i] = vis[j] = true;
			ans[C[j].indax] = D[i].indax;
			break;
		}
	//	cout << D[i].indax << " " << D[i].num << " " << each << " " << sum << endl;
	}
	for (int x = 1; x <= m; ++x)
	{
		if (vis[x]) continue;
		sum -= each;
	}
	return ;
}

inline void output()
{
	printf("%lld\n",sum);
	for (int i = 1; i <= m; ++i)
	{
		printf("%lld\n",ans[i]);
	}
	return ;
}

inline void solve()
{
	win();
	lose();
	return ;
}

signed main()
{
	get();
	solve();
	output();
	return 0;
}