这道题能用贪心吗?
查看原帖
这道题能用贪心吗?
541069
SuperCowHorse楼主2022/1/27 20:29

RT。

#include<bits/stdc++.h>
#define lo long long
using namespace std;
lo sx,sy,ex,ey,t,n,ans;
struct node
{
	lo time,beau,numb;
	double ffff;
}a[10005];
lo read()
{
	char c;
	lo sum=0;
	c=getchar();
	while(c>'9'||c<'0')
		c=getchar();
	sum=c-48;
	c=getchar();
	while(c>='0'&&c<='9')
	{
		sum=sum*10+c-48;
		c=getchar();
	}
	return sum;
}
bool cmp(node u,node v)
{
	return u.ffff>v.ffff;
}
int main()
{
	sx=read();sy=read();ex=read();ey=read();
	t=ex*60+ey-sx*60-sy;
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i].time=read();
		a[i].beau=read();
		a[i].numb=read();
		a[i].ffff=a[i].beau*1.0/a[i].time;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
		if(a[i].time<=t)
		{
			if(a[i].numb==0||t<=a[i].time*a[i].numb)
			{
				ans+=t/a[i].time*a[i].beau;
				t%=a[i].time;
			}
			else
			{
				ans+=a[i].numb*a[i].beau;
				t-=a[i].time*a[i].numb;
			}
		}
	printf("%lld",ans);
}
2022/1/27 20:29
加载中...