自动搬运

查看原文

来自洛谷，原作者为

	what_could_I_do **

搬运于2025-08-24 22:50:51，当前版本为作者最后更新于2023-10-04 10:28:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

很明显的贪心。

我们需要用尽可能少的价钱买下尽可能多的物品并用尽可能多的价钱卖出。

所以我们要先对题目给的序列进行排序，接下来用 $i$ 和 $j$ 表示序列的头尾两端，然后如果 $i$ 的交易次数比 $j$ 多，那么卖出的物品数量就是 $j$ 的次数，让 $j$ 减 $1$。如果 $j$ 的交易次数比 $i$ 多，那么卖出的物品数量就是 $i$ 的次数，$i$ 加 $1$。如果 $i$ 的价格已经与 $j$ 相同，就没必要交易了，退出。

CODE:

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
struct aaa
{
	long long a,b;
}c[100010];
inline bool cmp(aaa x,aaa y)
{
	return x.a<y.a;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		long long ans=0;
		scanf("%d",&n);
		for(register int i=1;i<=n;i++) scanf("%lld%lld",&c[i].a,&c[i].b);
		sort(c+1,c+n+1,cmp);
		int j=1,k=n;
		while(1)
		{
			if(c[j].a==c[k].a) break;
			if(c[j].b>c[k].b) ans+=(c[k].a-c[j].a)*c[k].b,c[j].b-=c[k].b,k--;
			else ans+=(c[k].a-c[j].a)*c[j].b,c[k].b-=c[j].b,j++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}