自动搬运

查看原文

来自洛谷，原作者为

	pzc2004 Прекрасное далёко, не будь ко мне жестоко

搬运于2025-08-24 21:58:20，当前版本为作者最后更新于2019-09-01 18:47:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路：这题就是一个贪心，先将每个休息站按照美味值从大到小排序，然后从头到尾扫一遍，能吃就一直吃到FJ追上来为止。

细节：要开long long！！！别问我是怎么知道的

代码：

#include <bits/stdc++.h>
using namespace std;
long long l,n,v1,v2,ans,a2;//v1为FJ的速度，v2为Bessie的速度，a2记录Bessie吃了多久的草
struct sb
{
	long long a,b;
}a[100001];
bool cmp(const sb &sb1,const sb &sb2)
{
	return sb1.b>sb2.b;
}
int main()
{
	scanf("%lld%lld%lld%lld",&l,&n,&v1,&v2);
	for(long long i=1;i<=n;i++)scanf("%lld%lld",&a[i].a,&a[i].b);
	sort(a+1,a+n+1,cmp);//排序（C++党的优越感）
	for(long long i=1;i<=n;i++)//从头往后扫
	{
		if(a[i].a*v2+a2<=a[i].a*v1)//如果Bessie到这块草地的时间加上她已经用来吃草的时间小于等于FJ到这块草地的时间
		{
			ans+=(a[i].a*v1-a[i].a*v2-a2)*a[i].b;//吃个痛快！
			a2=a[i].a*v1-a[i].a*v2;//将吃草的时间加上
		}
	}
	printf("%lld",ans);//输出
}