PAT-A最后一个问题。最后做出来...
贪婪，通过局部优化全局优化。
1. 该加油站按距离升序排列
2. 记录气体台当前所在index，目前的汽油。开支。在您的整个背部
3. 遍历中有两种情况：
1) 若发现油价比index更低的站next：
立即跳到该站（此时可能须要加油），不再继续遍历 —— 由于即使想要到达next后面的站，能够通过在next站购买更廉价的汽油来实现
2) 没有发现油价比index更低的站，则选择全部站中油价最低的站作为next:
此时考虑能否通过index抵达终点，若能。直接break, 不用管next; 若不能，则装满油。并行驶到next站.
4. 測试点2測试最大距离为0的情况 —— 即在起始点没有加油站。
代码：
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm> using namespace std; struct Station
{
double price;
int dis;
Station(double p, int d): price(p), dis(d) {}
friend bool operator <(const Station& a, const Station& b)
{
return a.dis < b.dis;
}
}; int main()
{
vector<Station> station;
double cmax, dest, davg, p;
int n, d;
int index = 0; // index indicate the station where they are.
double cost = 0, gas = 0;
cin >> cmax >> dest >> davg >> n;
for (int i = 0; i < n; ++ i)
{
cin >> p >> d;
station.push_back( Station(p, d) );
}
sort(station.begin(), station.end());
if (station[0].dis != 0)
{
cout << "The maximum travel distance = 0.00" << endl;
return 0;
} while ( true )
{
// 选择下一个站
double min_price = 2100000000;
int next = -1;
bool find_cheaper = false;
for (int i = index+1;
i<n && station[i].dis<dest && station[i].dis<=station[index].dis+cmax*davg;
++ i)
{
if (station[i].price <= station[index].price)
{
find_cheaper = true;
next = i;
break;
} else if (station[i].price < min_price)
{
min_price = station[i].price;
next = i;
}
}
// 选择加油方式
if (find_cheaper == true)
{
if (station[next].dis - station[index].dis > gas*davg) // 油无法到达该站
{
cost += ((station[next].dis-station[index].dis)/davg - gas) * station[index].price;
gas = 0;
} else
{
gas -= (station[next].dis-station[index].dis)/davg;
}
index = next;
} else if (next != -1) // 至少能够抵达下一个更贵的站
{
if (station[index].dis + cmax*davg >= dest)
{
break; // 跳出while循环
}
cost = cost + (cmax - gas) * station[index].price; // 装满油
gas = cmax - (station[next].dis - station[index].dis) / davg;
index = next;
} else
{
break;
}
} if (station[index].dis + cmax*davg >= dest)
{
cost = cost + ((dest-station[index].dis)/davg-gas)*station[index].price;
cout << setiosflags(ios::fixed) << setprecision(2) << cost;
} else
{
cout << "The maximum travel distance = " << setiosflags(ios::fixed) << setprecision(2) << station[index].dis + cmax*davg;
} return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。