求助
查看原帖
求助
561309
whl0807楼主2022/11/19 20:55

这道题做了很久,一直卡在75pts上

题目:旅行家的预算

评测记录

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	double dic1,c,dic2,jyz[103][3]={0};
	int n;
	cin>>dic1>>c>>dic2>>jyz[0][2]>>n;
	jyz[0][1]=0;
	jyz[n+1][1]=dic1;
	
	for(int i=1;i<=n;i++)
		cin>>jyz[i][1]>>jyz[i][2];
		
	for(int i=0;i<=n;i++)
	
		for(int j=i;j<=n;j++)
			if(jyz[i][1]>jyz[j][1])
			{
				double t=jyz[i][1];
				jyz[i][1]=jyz[j][1];
				jyz[j][1]=t;
				t=jyz[i][2];
				jyz[i][2]=jyz[j][2];
				jyz[j][2]=t;
			}
	
	double zxfy=0,syylc=0;

	for(int k=0;k<=n;)
	{
		if(jyz[k][1]+syylc>=dic1)
		{
			cout<<fixed<<setprecision(2)<<zxfy<<endl;
			return 0;
		}
		
		if(jyz[k][1]+c*dic2<jyz[k+1][1])
		{
			cout<<"No Solution"<<endl;
			return 0;
		}
		
		int zpy=k;
		
		for(int i=k+1;i<=n;i++)
		{
			if(jyz[k][1]+c*dic2<jyz[i][1])	break;
			
			if(jyz[i][2]<jyz[zpy][2])
				zpy=i;
		}
	
		if(zpy==k)
		{
			if(jyz[k][1]+c*dic2>=dic1)
			{
				zxfy+=(dic1-jyz[k][1]-syylc)/dic2*jyz[k][2];
				cout<<fixed<<setprecision(2)<<zxfy<<endl;
				return 0;
			}
			
			zxfy+=(c-syylc/dic2)*jyz[k][2];
			syylc=c*dic2;
			k++;
		 }
		else
		{
			zpy=k;
		 	for(int i=k+1;i<=n;i++)
			{
				if(jyz[k][1]+syylc<jyz[i][1])	break;
				if(jyz[i][2]<jyz[zpy][2])
					zpy=i;
			}
		
			if(zpy!=k)
			{
				syylc-=(jyz[zpy][1]-jyz[k][1]);
				k=zpy;
			}
			else
			{
				for(int i=k+1;i<=n;i++)
				{
					if(jyz[i][2]<jyz[k][2])
					{
						zpy=i;
						break;
					}
				}
				
				zxfy+=(jyz[zpy][1]-jyz[k][1]-syylc)/dic2*jyz[k][2];
				k=zpy;
				
			}
		}
	}
}

过路大佬帮忙看下,最后一点WA了,求助

2022/11/19 20:55
加载中...