求助,后四个点都过了,第一个点没过
查看原帖
求助,后四个点都过了,第一个点没过
1258423
YukiSprite楼主2024/1/21 12:03
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
void findMin(double *dist,double *price,double cap,double distPerL,int N,double petrolNow,int station,double minPrice);
int main()
{
	int N;
	double totalDist,cap,distPerL,price0,minPrice = 0,petrolNow = 0;
	scanf("%lf %lf %lf %lf %d",&totalDist,&cap,&distPerL,&price0,&N);
	double dist[N+2],price[N+2];
	dist[0] = 0;
	price[0] = price0;
	dist[N+1] = totalDist;
	price[N+1] = -10000000;
	for(int i=1;i<N+1;i++)
	{
		scanf("%lf %lf",&dist[i],&price[i]);
	}
	N += 2;
	int station=0;
	findMin(dist,price,cap,distPerL,N,petrolNow,station,minPrice);
	return 0;
}
void findMin(double *dist,double *price,double cap,double distPerL,int N,double petrolNow,int station,double minPrice)
{
	
//	printf("start minprice is %f\n",minPrice);
	double maxDist = cap*distPerL;
	for(int i=0;i<N-1;i++){
//	printf("maxdist is %f\n",maxDist);
//	printf("%f %f\n",dist[i+1],dist[i]);
		if(maxDist<(dist[i+1]-dist[i])){
			printf("No Solution");
			return;
		}	
	}
	
	if(station==N-1){
		printf("%.2lf",minPrice);
		return;
	}
// when to end
	else{
		int maxStation = 0;
		int detectend = 0;
		while(true){
//			printf("yici\n");
			if((dist[station+maxStation]-dist[station])>maxDist) {

				maxStation--;
				break;	
			}			
			if(station+maxStation>=N-1){
				detectend = 1;		
				break;
			} 
			maxStation++;
		}
//		printf("maxstation%d\n",maxStation);
//		find max station
		double tmp = price[N-1];
//		printf("detectend %d\n",detectend);
		if(detectend) price[N-1] = 1000000;
		int targetStation = station;
		double targetPrice = price[station];
//		printf("original targetprice%f targetstation%d station%d\n",targetPrice,targetStation,station);		
		for(int i=0;i<=maxStation;i++){
			if(price[i + station]<=targetPrice) {
				targetPrice = price[i+station];
				targetStation = i + station;
			}
		}
		price[N-1] = tmp;
//		printf("\ntargetprice%f targetstation%d station%d\n",targetPrice,targetStation,station);
		if(targetStation==station){
//			printf("detectend2 is %d\n",detectend);
			if(detectend){
				minPrice += ((petrolNow - (dist[N-1]-dist[targetStation])/distPerL)*price[station])>0?((petrolNow - (dist[N-1]-dist[targetStation])/distPerL)*price[station]):(-((petrolNow - (dist[N-1]-dist[targetStation])/distPerL)*price[station]));
				station = N-1;
				findMin(dist,price,cap,distPerL,N,petrolNow,N-1,minPrice);
			}
			else{
				
				minPrice += (cap-petrolNow)*targetPrice;
				petrolNow = cap - (dist[station+1]-dist[station])/distPerL;
//				printf("petrolNow is % lf price is %lf minprice is %lf station is %d\n",petrolNow,targetPrice,minPrice,station);
				findMin(dist,price,cap,distPerL,N,petrolNow,station+1,minPrice);
			}
		}else{
			if(petrolNow*distPerL>=dist[targetStation]-dist[station]){
				petrolNow -= (dist[targetStation]-dist[station])/distPerL;
//				printf("1 price is %lf minprice is %lf station is %d\n",targetPrice,minPrice,station);
				findMin(dist,price,cap,distPerL,N,petrolNow,targetStation,minPrice);
			}
			else{
					minPrice += ((dist[targetStation]-dist[station])/distPerL-petrolNow)*price[station];
					petrolNow = 0;
//					printf("2 price is %f minprice is %f station is %d disttargetstation is %f dist[station] is %f\n",price[station],minPrice,station,dist[targetStation],dist[station]);
//					printf("2 petrolNow=%f\n",petrolNow);
					findMin(dist,price,cap,distPerL,N,petrolNow,targetStation,minPrice);

				}
		}
//		in current envoriment,find best solution
	}
}
2024/1/21 12:03
加载中...