Sample Input

Sample Output

大意——有一个越野拉力赛，赛程包含很多个赛段。

由于各种各样的情况，所以汽车各赛段每英里的耗油量和油价都不一样。如今，给你每一个赛段的里程。油耗量，油价以及油箱容量，请你帮助參赛者决策。以便尽量少花油费。

如果參赛者一開始汽车里面没有油。每一个加油站的油无限以及參赛者必须完毕全部赛段才算完毕任务。

思路——显然这是一道贪心的题目。

那么贪心策略是如何的呢？由于完毕各个赛段的顺序一定，所以我们须要考虑该怎么样用油。

首先，假如某个赛段的总油耗量大于油箱容量。那么參赛者是不可能完毕本赛段的，亦即不可能完毕任务。再者，要油费最少，那么每次保证油箱里面的油廉价的最多就可以了。最后，要考虑的就是在第i站要不要加油。怎么加。加的有两种情况出现：1.在第i点把油加满，直到用完都没能找到比i点价格廉价的，那么果断加满。开到下一点去。2.在第i点把油加满，没用完之前可以找到比i点廉价的点，或者是到达终点，那么仅仅要将油加到能到达这个点就可以，然后直接到达这个点。

最后，把每一个点所需油费加起来就可以。

复杂度分析——时间复杂度:O(n^2),空间复杂度:O(n)

附上AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const double pi = acos(-1.0);
const double e = exp(1.0);
const int maxn = 100005;
LL mileage[maxn], consume[maxn], price[maxn];
// 存储每个赛段的长度，单位长度耗油量以及单位容量油价
int n; // 表示赛段的个数
LL capacity; // 坦克的容量

int main()
{
	ios::sync_with_stdio(false);
	int T; // 例子的个数
	scanf("%d", &T);
	while (T--)
	{
		bool flag = 0; // 标记是否达标，即每个赛段是否可以通过
		scanf("%d%lld", &n, &capacity);
		for (int i=0; i<n; i++)
		{
			scanf("%lld%lld%lld", &mileage[i], &consume[i], &price[i]);
			if (mileage[i]*consume[i] > capacity)
				flag = 1; // 赛段i耗油量大于存储的油量，坦克不足以支撑到
						  // 下一个赛段，故不可能完毕全部赛段
		}
		if (flag)
		{ // 全部油耗尽都不能到达下一个赛段。则失败
			printf("Impossible\n");
			continue;
		}
		LL min_price = 0; // 记录最小花费
		LL extra = 0; // 记录到达赛段i时坦克剩余油量
		for (int i=0; i<n;)
		{
			int j = i+1; // 从赛段i的下一个赛段開始寻找价格廉价的赛段
			int temp = mileage[i]*consume[i]; // 到达下一个廉价的赛段所须要的油量
			while (j<n && price[j]>=price[i] && capacity-temp>=mileage[j]*consume[j])
			{ // 向终点查找，直到找到一个比赛段i价格廉价的赛段j。或者是油耗尽了
				temp += mileage[j]*consume[j];
				j++;
			}
			if (j>=n || price[j]<price[i])
			{ // 找到赛段j的价格比赛段i廉价，仅仅要把油加到能到达赛段j就可以
				if (extra > temp) // 油非常多。不须要花钱买
					extra -= temp;
				else
				{
					min_price += (temp-extra)*price[i]; // 油不够，仅仅需买能达到赛段j的油就可以
					extra = 0; // 油箱的油全部用完
				}
				i = j;
			}
			else
			{ // 油耗尽了都没有找到比赛段i价格廉价的赛段
				min_price += (capacity-extra)*price[i]; // 加满油，到下一个赛段
				extra = capacity-mileage[i]*consume[i]; // 到下一个赛段还剩多少油
				i++;
			}
		}
		printf("%lld\n", min_price);
	}
	return 0;
}