区间贪心算法,后一个区间的起点较前一区间偏移多少,区间终点也会偏移多少,所以不用考虑油箱容积的变化。另外浮点数需使用double,float不能通过测试。
#include <iostream> #include <algorithm> using namespace std; struct station { double price; int distance; }; bool compare(station a, station b) { return a.price <= b.price; } int main() { int cmax, d, davg, n; while (cin >> cmax >> d >> davg >> n) { // 注意 while 处理多个 case // cout << a + b << endl; station stationList[n]; for (int i = 0; i < n; i++) { cin >> stationList[i].price >> stationList[i].distance; } sort(stationList, stationList + n, compare); bool way[d + 1]; for (int i = 0; i < d + 1; i++) way[i] = false; int farest = cmax * davg; double price = 0; //从油价最低的加油站开始,尽肯能多的去规划里程 for (auto station : stationList) { int distance = 0; for (int j = station.distance + 1; j <= d && j <= station.distance + farest; j++) { if (way[j] == false) { way[j] = true; distance++; } } price += distance / (davg * 1.0)* station.price; } bool finish = true; double allDistance = 0; for (int i = 1; i < d+ 1; i++) { if (way[i] == false) { finish = false; break; } else allDistance++; } if (finish == true) printf("%.2f\n", price); else printf("The maximum travel distance = %.2f\n", allDistance); } } // 64 位输出请用 printf("%lld")// 64 位输出请用 printf("%lld")