#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
const int inf = 999999;
struct station{
double price, dis;
};
bool cmp1(station a, station b){
return a.dis < b.dis;
}
int main(){
double Cmax, D, Davg;
int N;
scanf("%lf%lf%lf%d", &Cmax, &D, &Davg, &N);
vector<station> sta(N+1);
sta[0] = {0.0, D};
for(int i = 1; i <= N; i++){
scanf("%lf%lf", &sta[i].price, &sta[i].dis);
}
sort(sta.begin(), sta.end(), cmp1);
double nowdis = 0.0, maxdis = 0.0, nowPrice = 0.0, totalPrice = 0.0, leftdis = 0.0;
if(sta[0].dis != 0){
printf("The maximum travel distance = 0.00");
return 0;
}else{
nowPrice = sta[0].price;
}
while(nowdis < D){
maxdis = nowdis + Cmax*Davg;
double minPrice = inf, minPriceDis = 0;
int flag = 0;
for(int i = 1; i <= N && sta[i].dis <= maxdis; i++){
if(sta[i].dis <= nowdis) continue;
if(sta[i].price < nowPrice){
totalPrice += (sta[i].dis - nowdis - leftdis) * nowPrice / Davg;
leftdis = 0.0;
nowPrice = sta[i].price;
nowdis = sta[i].dis;
flag = 1;
break;
}
if(sta[i].price < minPrice){
minPrice = sta[i].price;
minPriceDis = sta[i].dis;
}
}
if(flag == 0 && minPrice != inf){
totalPrice += (Cmax - leftdis/Davg) * nowPrice;
leftdis = maxdis - minPriceDis;//(Cmax*Davg - (minPriceDis - nowdis));
nowPrice = minPrice;
nowdis = minPriceDis;
}
if(flag == 0 && minPrice == inf){
//nowdis += Cmax * Davg;
printf("The maximum travel distance = %.2f", maxdis);
return 0;
}
}
printf("%.2f", totalPrice);
return 0;
}
A1033 To Fill or Not to Fill (25 分)
原文:https://www.cnblogs.com/tsruixi/p/11847673.html