题目来源：http://www.tsinsen.com/A1122
A1122. 旅行家的预算
时间限制：1.0s 内存限制：256.0MB
试题来源
NOIP1999 提高组
问题描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入格式
第一行为4个实数D1、C、D2、P与一个非负整数N；
接下来N行，每行两个实数Di、Pi。
输出格式
如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否则输出“No Solution”（不含引号）。
样例输入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出
26.95
-----------------------------------------------------
解题思路
贪心
在加油站i加满油能到达的所有加油站中，如果存在油价比i低的加油站j，则在加油站i把油加到恰好能开到加油站j就行
否则在加油站j把油加满开到下一个加油站
-----------------------------------------------------
代码
// 贪心
// 在加油站i加满油能到达的所有加油站中，如果存在油价比i低的加油站j，则在加油站i把油加到恰好能开到加油站j就行
// 否则在加油站j把油加满开到下一个加油站
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
struct station {
double dis,pri;
bool operator< (const station &b) const
{
return dis<b.dis; // 按照距离升序
}
};
int main()
{
#ifndef ONLINE_JUDGE
ifstream fin("A1122.txt");
double d1,c,d2,p;
int n,i,j;
fin >> d1 >> c >> d2 >> p >> n;
station tmp;
vector<station> sta;
tmp.dis = 0;
tmp.pri = p;
sta.push_back(tmp);
tmp.dis = d1;
tmp.pri = 0;
sta.push_back(tmp); // 把起点和终点也当做加油站加入序列中
for (i=0; i<n; i++)
{
fin >> tmp.dis >> tmp.pri;
sta.push_back(tmp);
}
fin.close();
sort(sta.begin(), sta.end()); // 按距离升序
double oil = 0, ans = 0; // 当前剩余油量和加油花费
int pos = 0; // 当前位置
double currentDis = 0, currentPri = p; // 当前加油站的距离和油价
bool has_next = false; // 是否能达到下一个加油站
while (pos!=n+1)
{
has_next = false;
currentDis = sta.at(pos).dis;
currentPri = sta.at(pos).pri;
for (j=pos+1; j<n+2; j++)
{
if (sta.at(j).dis-currentDis>c*d2)
{
break;
}
if (sta.at(j).pri<currentPri) // 找到油价更便宜的j加油站
{
has_next = true; // 找到了一箱油可达的加油站
pos = j;
if (oil>=(sta.at(j).dis-currentDis)/d2) // 油箱里现存的油已经足够开到j加油站
{
oil -= (sta.at(j).dis-currentDis)/d2;
}
else // 现存的油不够开到j加油站
{
ans += ((sta.at(j).dis-currentDis)/d2-oil)*currentPri; // 补上在pos加油站加油的油钱
oil = 0; // 把油用光
}
break;
}
}
if (!has_next) // 一箱油的车程内没有油价更便宜的加油站
{
if (sta.at(pos+1).dis-currentDis>c*d2) // 一箱油开不到最近的加油站
{
break;
}
else
{
ans += (c-oil)*currentPri; // 在当前加油站把油加满
oil = c-(sta.at(pos+1).dis-currentDis)/d2;// 路上的油耗
pos++;
}
}
}
if (pos!=n+1)
{
cout << "No Solution";
}
else
{
cout << fixed << setprecision(2) << ans;
}
return 0;
#endif
#ifdef ONLINE_JUDGE
double d1,c,d2,p;
int n,i,j;
cin >> d1 >> c >> d2 >> p >> n;
station tmp;
vector<station> sta;
tmp.dis = 0;
tmp.pri = p;
sta.push_back(tmp);
tmp.dis = d1;
tmp.pri = 0;
sta.push_back(tmp); // 把起点和终点也当做加油站加入序列中
for (i=0; i<n; i++)
{
cin >> tmp.dis >> tmp.pri;
sta.push_back(tmp);
}
sort(sta.begin(), sta.end()); // 按距离升序
double oil = 0, ans = 0; // 当前剩余油量和加油花费
int pos = 0; // 当前位置
double currentDis = 0, currentPri = p; // 当前加油站的距离和油价
bool has_next = false; // 是否能达到下一个加油站
while (pos!=n+1)
{
has_next = false;
currentDis = sta.at(pos).dis;
currentPri = sta.at(pos).pri;
for (j=pos+1; j<n+2; j++)
{
if (sta.at(j).dis-currentDis>c*d2)
{
break;
}
if (sta.at(j).pri<currentPri) // 找到油价更便宜的j加油站
{
has_next = true; // 找到了一箱油可达的加油站
pos = j;
if (oil>=(sta.at(j).dis-currentDis)/d2) // 油箱里现存的油已经足够开到j加油站
{
oil -= (sta.at(j).dis-currentDis)/d2;
}
else // 现存的油不够开到j加油站
{
ans += ((sta.at(j).dis-currentDis)/d2-oil)*currentPri; // 补上在pos加油站加油的油钱
oil = 0; // 把油用光
}
break;
}
}
if (!has_next) // 一箱油的车程内没有油价更便宜的加油站
{
if (sta.at(pos+1).dis-currentDis>c*d2) // 一箱油开不到最近的加油站
{
break;
}
else
{
ans += (c-oil)*currentPri; // 在当前加油站把油加满
oil = c-(sta.at(pos+1).dis-currentDis)/d2;// 路上的油耗
pos++;
}
}
}
if (pos!=n+1)
{
cout << "No Solution";
}
else
{
cout << fixed << setprecision(2) << ans;
}
return 0;
#endif
}