贪心思维

发表于2021-10-25更新于2021-10-25阅读次数

Neko’s loop HDU - 6444

题意：有n个城市, 在每个城市中你可以选择花费a[ i ]的价格买一个能量块, 也可以选择以a[ i ]的价格卖出一个能量块(前提是你要有能量块可以卖). 你会从1号城市依次走到n号城市, 每次可以选择买或者卖或者什么也不做. 在初始你有无限多的钱的前提下, 问你能获得的最大利润, 以及在最大利润的前提下最小的买卖次数.
————————————————
版权声明：本文为CSDN博主「逍遥Fau」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_45799835/article/details/108682519

·
·

·
·
·
·
·
·
·

·
·
·
·
·

·
·

·
·
·
·
·

·
·
·
·
·

·
解题思路:
首先如果一件物品买了后再卖了能赚钱, 则我们一定会采取这种方案, 因为题目要求最大利润优先, 最小的买卖次数则是不做无意义的买卖, 如花费x元购买能量块后又以x元卖出.

贪心思路:
因为我们难以决定在第i个城市我们采取怎么样的操作是最优的, 所以不妨对于每一个城市, 我们都认为我们可以从该城市买入能量块, 并且在j城市(j>i)卖出(但是在卖出之前, 我们认为我们在i城市什么也没做). 而j城市的能量块价格是一定为a[j]的, 所以此时我们如果要卖出能量块, 一定要以最小的价格在i城市买入能量块. 对于买入能量块的城市i, 我们可以采用小顶堆来维护, 而城市j的确定则是难点.

假设我们现在存在一个小顶堆, 里面存放的元素代表可以用x的价格买入能量块(即所有的i城市), 当我们到达j城市, 此时如果满足a[j] > heap.top(), 我们此时选择卖出一定可以赚到钱, 且为一种优质策略.
此时我们的利润变化为: res = res + a[j] - x. (记为*式)

但是我们无法保证后续不会存在城市k (k>j), 满足a[k] > a[j], 则我们发现不如在k城市卖出刚才的能量块, 所以我们此时就要有一种反悔策略, 即: 刚才的能量块不选择在j城市卖出(即我们又可以以a[j]的价格买入能量块, 应当把a[j]入堆), 而在k城市卖出该能量块. 本身我们花费了x元买入, 卖出得到了a[j]元, 变成了x元买入, a[k]元卖出. 则利润变化为: res = res - a[j] + a[k]. 做一个变形, 类比于*式, 我们得到 res = res + a[k] - a[j].
从操作次数的角度看, 我们在j城市买入能量块, 在k城市卖出, 结合之前i城市的操作, 相当于我们在j城市卖了一次, 又买了一次. 所以在j城市的操作并不是合法操作, 不应计算在结果中.

而从利润的角度看, 我们获得的利润可以看作买了i, 在j卖出, 又在j买入, 在k卖出. 我们发现这两种情况的利润遵循相同的公式.
————————————————
版权声明：本文为CSDN博主「逍遥Fau」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_45799835/article/details/108682519

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:37
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-25 13:07:14
*/
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll ca;cin>>ca;
    while(ca--){
        ll n;cin>>n;
        priority_queue<ll,vector<ll>,greater<ll>> q;
        map<ll,ll> mp;
        ll ans=0,cnt=0;
        for(ll i=1;i<=n;i++){
            ll x;cin>>x;
            if(!q.empty() && q.top()<x){
                ll sell=q.top();q.pop();
                ans+=x-sell;
                if(mp.count(sell)){
                    if(--mp[sell]==0)  mp.erase(sell);
                    q.push(sell);
                }
                else  cnt++;
                mp[x]++;
            }
            q.push(x);
        }
        cout<<ans<<" "<<cnt*2<<endl;
    }
    return 0;
}