[数据结构与算法]51nod3108 小明爱换钱

3108 小明爱换钱

小明非常喜欢换钱，这天他想到一个换钱游戏，游戏规则是这样的，从一件价值1元的小物品开始。然后，经过反复的交换，不断增加手中物品的价值。在每次兑换中，如果您的物品价值大于或等于R元，您可以兑换为V元，花费时间成本为T分钟。现在，你的任务是用尽量少的时间，帮助小明兑换到大于等于W元。

输入

第一行中的两个整数N, M (1 <= N <= 10^5, 1 <= M <= 10^9)表示可用交换的数量和
最终金钱的期望值。
接下来是N行，每一行描述一个有3个整数Vi, Ri, Ti (1 <= Ri <= Vi <= 10^9, 1 <= 
Ti <= 10^9)的交换。

输出

输出一个数字，表示最少花费时间，如果不可以完成任务，输出"-1".

数据范围

对于10%的数据，1<= N <= 8， 1 <= M <= 10^9
对于50%的数据，1 <= N<= 1024， 1 <= M <= 10^9
对于100%的数据，1 <= N <= 100000， 1 <= M <= 10^9
1 <= Ri <= Vi <= 10^9, 1 <= Ti <= 10^9

输入样例

输入样例1
3 10
5 1 3
8 2 5
10 9 2
输入样例2
4 5
2 1 1
3 2 1
4 3 1
8 4 1
输入样例3
5 9
5 1 1
10 4 10
8 1 10
11 6 1
7 3 8

输出样例

输出样例1
-1
输出样例2 
4
输出样例3
10

解析：

我们先来思考如何利用暴力枚举，统计所有可能的兑换情况，并找出用时最短的方案呢？

初始时物品价值为?1，枚举所有可能发生的兑换，经过兑换后，物品的价值变了，同时消耗的时间要加上本次兑换所需的时间。然后再递归处理，直到物品的价值大于?W?为止，记录所有可能的兑换情况所用的时间。输出其中用时最少的。

这个暴力的方法复杂度是指数级的，我们考虑如何能够优化这个算法。如果我们能够按照总耗时从小到大枚举所有兑换的情况，那么只要第一次出现物品价值大于?W，那么当前答案就是最优的。

另外考虑这种情况，在按照用时从小到大枚举的过程中，每个兑换的策略其实只需要处理?1?次，这是因为如果之前有耗时更少的方案可以采用当前的兑换规则，则得到的结果总耗时一定比当前更优，并且物品价值相同。

我们用一个优先队列来辅助解决这个问题。先把所有兑换规则，按照物品价值?RiRi?排序。初始化一个情况，此时总耗时为?0，并且当前物品价值为?1，放入优先队列，优先队列中元素的排序按照总耗时来的，耗时少的排在队列顶部。

每次从优先队列里面拿出花费时间最少的情况?mins，遍历所有兑换规则，把所有物品价值小于等于?mins?的，同?mins?进行结合计算。重新放回到优先队列中去，一旦兑换规则要求的物品价值?RiRi?大于?mins?的物品价值，则停止。如何结合当前物品和?mins呢？将新的价值设为规则可以兑换的物品价值?Vi，总耗时设为?mins 的总耗时 + 执行当前兑换规则的耗时?Ti。

如此循环，直到第一次遇到?minsmins?的价值大于等于m为止，此时?minsmins?的耗时就是答案。

注意，由于这个过程中，每一个兑换规则只会同取出的 ?minsmins?结合计算一次。因此总的复杂度为 ?O(nlogn)。

这里用如下数据来解释一下上面的过程：

4 5
2 1 1
3 2 1
4 3 1
8 4 1

首先我们对4个兑换规则排序。

优先队列里面存储的是?pair<int,int>，pair 的?first 保存物品价值，second?保存总的耗时。优先队列本身排序按照?second 来 。重载每次弹出时间最小的?pair<int,int>。

第一次弹出来是?pair<1,0>，得到?pair<2,1>，放进队列，弹出pair<2,1>，得到?pair<3,2>，放进队列，弹出?pair<3,2>，得到?pair<4,3>，放进队列，弹出pair<4,3>，得到?pair<8,4>，放进队列，弹出?pair<8,4>，8?大于等于?5，返回时间?4，结束。

放代码：

#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
 
const int MAX_SIZE=100005;
 
struct node{
    int value;
    int spend;
    node(int _value=0,int _spend=0):value(_value),spend(_spend){}
    bool operator < (const node &r)const{
        return spend > r.spend;
    }
 
};
int V[MAX_SIZE];
int R[MAX_SIZE];
int T[MAX_SIZE];
 
 
 
int main(){
    //freopen("in.text","r",stdin);
    int n,m;
    int ans=-1;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d%d%d",V+i,R+i,T+i);
    }
    priority_queue<node> que;
    que.push(node(1,0));
    while(!que.empty()){
        node temp_node=que.top();
        que.pop();
        if(temp_node.value>=m){
            ans=temp_node.spend;
            break;
        }
        for(int i=0;i<n;i++){
            if(temp_node.value<V[i]&&temp_node.value>=R[i]){
                que.push(node(V[i],temp_node.spend+T[i]));
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}