文章
1
粉丝
35
获赞
2
访问
1.2k
/*
我们假设会经过所有的加油站
我们可以假装持有价格高得油,一旦遇到价格低的就进行替换
在经过加油站的时候,我们补充该加油站的油(注意是假设补充,具体是否补充要看之后有没有遇见更加便宜的油)
比如,我们的油箱在遇到价值4快的加油站时,还剩下2块钱的油和5块钱的油,这说明之前假装补充的5块钱的油
是可以被四块钱的油所替代,因此
我们就可以补充油
注意计算cost的时候要以实际花费的油为准,而不是在补充油的时候进行计算
*/
#include<bits/stdc++.h>
using namespace std;
// double判断相等需要用一个接近无穷小
#define eps 1e-8
//加油站结构体
struct Station{
double price, distance;
}s[200];
bool cmp(Station s1, Station s2){
return s1.distance < s2.distance;
}
int main(){
double cmax, d, davg;
int n;
while (scanf("%lf%lf%lf%d", &cmax, &d, &davg, &n) != EOF){
// 从1开始,较为清晰
for (int i = 1; i <= n; i++){
scanf("%lf%lf", &s[i].price, &s[i].distance);
}
//终点看作特殊的加油站
s[n+1].distance = d;
s[n+1].price = 0;
//注意这里的上下界
sort(s+1, s+1+n+1, cmp);
//双端队列,一方面弹出最低价格的油作为消耗;另一方面弹出最高价格的油作为替换
deque<pair<double, double>> d;
doub...
登录后发布评论
暂无评论,来抢沙发