比赛 贪心题目练习 评测结果 AAAA
题目名称 旅行家的预算 最终得分 100
用户昵称 duck 运行时间 0.013 s
代码语言 C++ 内存使用 3.64 MiB
提交时间 2025-03-22 10:18:35
显示代码纯文本
#include<bits/stdc++.h> 
using namespace std;
double d1,c,d2,s,V,ans,minn; 
int n,now,flag;
struct duck{
	double d,p;
}a[12];
bool cmp(duck x,duck y){
	return x.d<y.d;
}
int main()
{
    freopen("lyuxing.in","r",stdin);
    freopen("lyuxing.out","w",stdout);
	cin>>d1>>c>>d2>>a[0].p>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].d>>a[i].p;
	s=c*d2; 
	a[n+1].d=d1;
	sort(a+1,a+1+n,cmp);	
	for(int i=1;i<=n+1;i++)
	{
		if(a[i].d-a[i-1].d>s)
		{
			printf("No Solution");
			return 0;
		}
	}
	
	while(1){
		int next,k;
		minn=79868;
		flag=1;
		for(int i=now+1;a[i].d-a[now].d<=s && i<=n;i++){
			if(a[i].p<=a[now].p && flag)
			{
				next=i;
				ans+=((a[i].d-a[now].d)/d2-V)*a[now].p;
				flag=0; 
				V=0;
				break;
			}
			if(minn>a[i].p)  
			{
				minn=a[i].p;
				k=i;
			}
		}
		if(flag){
			if(d1-a[now].d<=s)
			{
				ans+=((d1-a[now].d)/d2-V)*a[now].p;
				break;
			}
			else   
			{
				next=k;
				ans+=a[now].p*(c-V);
				V=c; 
				V-=(a[k].d-a[now].d)/d2; 
			}
		}
		now=next;   
	}
	printf("%.2lf",ans);
	return 0; 
}