HDU 6438"Buy and Resell"（贪心+优先级队列）

•参考资料

　　[1]:HDU6438（优先队列+思维）

•题意

　　有n个城市，第 i 天你会达到第 i 个城市；

　　在第 i 个城市中，你可以用 a_i 元购买一个物品，或者用 a_i元卖掉一个物品，你可以同时保存多个物品。

　　最开始你身上没有物品，但是有无限的金钱；

　　让你求从城市 1 走到城市 n，最大的收益以及最少的交易次数。

•题解

　　假设你当前在第 i 个城市，这个城市的物价为 $a_i$ 元；

　　但是你要不要购买这个物品呢？

　　因为我们不确定第 i+1~n 个城市是否有物价高于 $a_i$ 的城市；

　　所以，我们可以选择先将 $\{i,a_i \}$ 加入购物车；

　　如果这之后存在更高物价的城市，就将 $\{i,a_i \}$ 下单，然后转手就卖；

　　假设第 j 个城市的物价 $a_j > a_i$；

　　那么，我们将 $\{i,a_i \}$ 下单，并以 $a_j$ 的价格出售，获得 $a_j-a_i$ 元的利润；

　　此时，第 $i,j$ 城市已经进行了一次操作，按理说不能在做其他操作了；

　　但是，如果你来到的下一个 k 城市的物价 $a_k > a_j > a_i$ 呢？

　　是不是将 $a_i$ 在此处卖更划算？

　　我们考虑一下，虽然 j 城市做了卖这个操作，但是我们还是可以将其加入到购物车中的；

　　因为，如果遇到比 $a_j$ 更大的物价，我们可以反悔一下，在第 j 个城市不出售 $a_i$；

　　而是在物价更高的 k 城市出售 $a_i$，这种决策才能获得更高的利润 $a_k-a_i$；

　　但是，你会发现 $a_k-a_i = (a_j-a_i)+(a_k-a_j)$，也就是说，就算是 $a_i$ 在 j 城市出售，也可以将 $\{ j,a_j \}$ 加入到购物车中；

　　只不过，在第 k 个城市出售 $a_j$ 并不是真的将 $a_j$ 卖出，而是将 $a_i$ 卖出；

　　但是，将 $a_i$ 卖出后，$a_j$ 依旧应该存在于购物车中，所以，我们要将 $\{ j,a_j\}$ 加入购物车两次；

　　并且，我们希望购物车按照从小到大的顺序排列，因为这样的话，遇到新城市，我们可以优先下单物件低的以此来获得更大的利润；

　　考虑到物品按照价格升序排列，我们可以用优先级队列；

•Code

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define mem(a,b) memset(a,b,sizeof(a))

 const int maxn=1e5+;

 int n;

 int a[maxn];

 struct Heap

 {

     int v;

     bool op;///op == 1 : 当前这个物品作为了中转物品

     bool operator < (const Heap &obj)const

     {

         if(v != obj.v)

             return v > obj.v;

         return op < obj.op;///中转物品优先

     }

 };

 priority_queue<Heap >q;

 void Solve()

 {

     while(!q.empty())

         q.pop();

     ll ans=;

     int cnt=;

     for(int i=;i <= n;++i)

     {

         if(!q.empty() && q.top().v < a[i])

         {

             Heap tmp=q.top();

             q.pop();

             ans += a[i]-tmp.v;

             if(!tmp.op)///如果tmp为非中转物品，那么在此处就有一次交易操作

                 cnt++;

             q.push({a[i],true});

         }

         q.push({a[i],false});

     }

     printf("%lld %d\n",ans,cnt<<);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i <= n;++i)

             scanf("%d",a+i);

         Solve();

     }

     return ;

 }

巴特西

HDU 6438"Buy and Resell"（贪心+优先级队列）

•参考资料

•题意

•题解

•Code

最新文章

热门文章