蓝桥杯 算法训练 旅行家的预算

问题描述

解题思路

贪心算法：在最大行驶距离内寻找比当前便宜的加油站,然后判断是否能一次到达,不能的话先加满,然后一个一个判断直到剩下的油量不足到下一个加油站就加油，加适量。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
double d[10000], p[10000];

int main(){
	double D1, C, D2;
	int N;
	cin >> D1 >> C >> D2 >> p[0] >> N;
	d[N+1] = D1;
	for(int i = 1; i <= N; i++){
		cin >> d[i] >> p[i];
	}
	double remain = 0, cost = 0;
	int pos = 0;
	do{
		bool found = false;
		for(int i = pos + 1; i <= N+1 && d[i] <= d[pos] + C*D2; i++){
			if(p[i] < p[pos]){
				if(d[pos] + remain*D2 >= d[i]){
					remain -= (d[i] - d[pos])/D2;
				}
				else{
					cost += ((d[i] - d[pos])/D2 - remain) * p[pos];
					remain = 0;
				}
				pos = i;
				found = true;
				break;
			}
		}
		
		if(!found){
			cost += (C - remain) * p[pos];
			remain = C - (d[pos+1] - d[pos])/D2;
			if(remain < 0) {
				cout << "No Solution";
				return 0;
			} 
			else pos++;
		}
	}while(pos <= N);
	printf("%.2lf",cost);
	return 0;
}