#5WA,求助
查看原帖
#5WA,求助
1507112
Notam楼主2024/10/10 22:15
#include <stdio.h>
int main()
{
	double length,c,lg,pst,sum=0;
	int n;
	scanf("%lf %lf %lf %lf %d",&length,&c,&lg,&pst,&n);
	double d[n+2],p[n+1],puse[n+1],duse[n+2];
	d[0]=0;
	d[n+1]=length;
	p[0]=pst;
	
	/*将加油站按先后排列*/
	
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&d[i],&p[i]);
		for(int j=i;j>0;j--)
		{
			if(d[j]>=d[j-1])
			    continue;
			d[j-1]+=d[j];
			p[j-1]+=p[j];
			d[j]=d[j-1]-d[j];
			p[j]=p[j-1]-p[j];
			d[j-1]-=d[j];
			p[j-1]-=p[j];
		}
	}
	
	/*通过站点间隔检测是否无解*/
	
	for(int i=0;i<=n;i++)
	{
		puse[i]=p[i];
		duse[i]=d[i];
		if(d[i+1]-d[i]>c*lg)
		{
			printf("No Solution");
			return 0;
		}
	}
	duse[n+1]=d[n+1];
	
	/*通过“将油铺在路上”覆盖全路面来求各站点油的使用路程*/
	
	for(int i=0;i<=n;i++)
	{
		int max;
		double maxn=0;
		for(int j=0;j<=n;j++)
			if(maxn<puse[j])
			{
				maxn=puse[j];
				max=j;
			}
		duse[max+1]=d[max]+c*lg;//求油费最贵站点
		if(duse[max+1]>length)
		    duse[max+1]=length;
		duse[max]=d[max];
		for(int k=max;k>0;k--)
		    if(duse[k]>duse[max])
		        duse[k]=duse[max];
		for(int k=max;k<n;k++)
		    if(duse[k]<duse[max])
		        duse[k]=duse[max];//将该站点的油铺到路上,覆盖更贵的油
        puse[max]=0;
	}
	duse[n+1]=length;
	for(int i=0;i<=n;i++)
		sum+=(duse[i+1]-duse[i])*p[i]/lg;//计算最上面一层油的总价值
	printf("%.2lf",sum);
	return 0;
}
2024/10/10 22:15
加载中...