题意：比赛的时候想了各种的贪心方案，最后还是没有把这题搞出来......废话不多说，题目给定了一条条给定了顺序的路径，这些路径是后面要一一走过的，每条路径有一个长度，单位长度消耗汽油的量以及该条公路上加油站的汽油单价。告诉你路径条数N，油箱容积K，问如何安排加油是的行走完所有路径的花费最少。
解法：该题有一个很巧妙的解法就是每到一个油站都加满油箱，队列里面保留了走过前面路径后保留的最便宜的油，每次从队列中取出最便宜的油行进这一段路程。在维持一个汽油价格单调递增时，具体过程如下：
1.当队尾不为空时，每次从队尾向前遍历，如果元素单价高于当前路线加油站的汽油单价，替换之，知道遇到价格比其低的汽油或者队列为空位置。
2.从队列中从前往后选择合适的汽油来行进该段路劲，并且更新价格。代码如下：
#include#include #include #include #include #include using namespace std;int N, K;typedef long long LL;struct road { int len, cpm, pri;}e[100005];struct gas { int vol, pri; gas(int v, int p) : vol(v), pri(p) {} gas() {}};deque dq;int vol;void solve() { LL ret = 0; vol = 0; while (!dq.empty()) { dq.pop_front(); } for (int i = 0; i < N; ++i) { while (!dq.empty() && dq.back().pri > e[i].pri) { vol -= dq.back().vol; dq.pop_back(); } dq.push_back(gas(K-vol, e[i].pri)); // 以上维护好一个单调递增的汽油序列 int nd = e[i].len * e[i].cpm; // 需求一定是一个不大于K的数值 vol = K - nd; while (nd) { gas & cur = dq.front(); // 引用队首的汽油 int Min = min(nd, cur.vol); cur.vol -= Min, nd -= Min; ret += 1LL * Min * cur.pri; if (!cur.vol) dq.pop_front(); } } printf("%lld\n", ret);}int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d %d", &N, &K); bool flag = true; for (int i = 0; i < N; ++i) { scanf("%d %d %d", &e[i].len, &e[i].cpm, &e[i].pri); if (1LL * e[i].len * e[i].cpm > K) { // 可能会溢出 flag = false; } } if (!flag) { puts("Impossible"); continue; } solve(); } return 0;}