p1016求帮助,75分!
  • 板块学术版
  • 楼主Henry246790
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/9/29 19:53
  • 上次更新2023/10/27 09:31:50
查看原帖
p1016求帮助,75分!
437873
Henry246790楼主2022/9/29 19:53
#include <bits/stdc++.h>
using namespace std;

const int NR=505;
const int MR=10;

double L,C,l1,P;   //城市距离,油箱容量,每升油里程,出发点油价
int N;   //加油站数目
struct gap{
	double d;   //d:该加油站与出发点距离
	double p;   //p:该加油站油价
}sta[10];
double pay=0,now=0;  //所需费用,现有油量 
int stay=0;  //现在在哪一站 
bool check=0;  //判断是否执行else中的for循环 

bool cmp(gap x,gap y){
	return x.d<y.d; 
}



int main(){
	cin>>L>>C>>l1>>P>>N;
	sta[0].d=0;  //起点为sta[0] 
	sta[0].p=P;
	sta[N+1].d=L;  //终点为sta[N+1] 
	sta[N+1].p=-999999; 
	for(int i=1;i<=N;i++){  //输入后若加满油都从前一个站到不了后一个站则无解 
		cin>>sta[i].d>>sta[i].p;
		if(C*l1<sta[i].d-sta[i-1].d){
			cout<<"No Solution";
			return 0;
		}
	} 
	if(C*l1<sta[N+1].d-sta[N].d){  //若加满油无法从终点之前一站到终点,无解 
		cout<<"No Solution";
		return 0;
	}

	sort(sta+1,sta+N+2,cmp);  //各加油站距起点距离从小到大排序 

	for(int i=0;i<=N;i++){   
		if(i<stay) continue;  //如果i比所在站靠前 
		double need=(sta[i+1].d-sta[i].d)/l1;  //从第i站到第i+1站所需油量 
		if(sta[i].p>=sta[i+1].p){  //如果第i站油费比第i+1站高,就加到可以到下一站即可 
			if(now<need){  
				pay+=(need-now)*sta[i].p;
				now=0;
				stay++;
			}	 
			else{
				now-=need;
				stay++;	
			} 
		}
		else{  //如果第i站油价比第i+1站低 
			for(int j=i;j<=N;j++){  //判断是否第i站后面有油价比sta[i].p低的j+1站且sta[j+1].d-sta[i].d<=C*l1(可以抵达) 
				if(sta[j+1].p<=sta[i].p&&sta[j+1].d-sta[i].d<=C*l1){
					pay+=(sta[j+1].d-sta[i].d)/l1*sta[i].p;
					now=0;
					stay=j+1;  //若有,则抵达第j+1站,并退出当前循环 
					check=1;   
					break;
				}
			}
			if(check){
				check=0;
				continue;   //开启j+1到j+2的判断 
			}
			pay+=(C-now)*sta[i].p;  //若没有,则加满油 
			now=C;
			now-=need;
			stay++;
		}	
	}

	//cout<<pay;
	printf("%.2lf",pay);

	return  0;

}


2022/9/29 19:53
加载中...