HDU6438购买和转售（贪心+集合-multiset）-CCPC2018网络赛

1.问题描述

Power Cube用作外来力量的藏身之处。有n个城市编号1,2，...，n允许交易它。第i个城市的Power Cube的交易价格是每立方体ai美元。Noswal是一个狡猾的商人，他想通过购买和转售Power Cubes来悄悄赚钱。为避免被警方发现，Noswal将前往第i个城市并在第i天选择以下三个选项中的一个：

花一美元购买一个Power Cube
如果他有至少一个Power Cube，则转售一个Power Cube并获得ai美元
没做什么

显然，Noswal可以同时拥有多个Power Cubes。去了n个城市之后，他会回家并远离警察。他想知道他可以赚取的最大利润。同时，为了降低风险，他希望尽量减少交易时间（包括买卖）以获得最大利润。Noswal是一个狡猾而又成功的商人，因此你可以假设他在开始时拥有无限金钱。

2.输入

有多个测试用例。第一行输入包含正整数T（T≤250），表示测试用例的数量。对于每个测试用例：
第一行有一个整数n。（1≤ñ≤10五）
第二行有n个整数a1，a2，...，其中ai表示第i个城市的Power Cube的交易价格（买入或卖出）。（1≤一个一世≤109）
保证所有n的总和不超过五×10五。

3.产量

对于每种情况，打印一行有两个整数 - 最大利润和最小交易次数以获得最大利润。

4.样本输入

3

4

1 2 10 9

5

9 5 9 10 5

2

2 1

5.样本输出

16 4

5 2

0 0

6.暗示

In the first case, he will buy in 1, 2 and resell in 3, 4. profit = - 1 - 2 + 10 + 9 = 16
In the second case, he will buy in 2 and resell in 4. profit = - 5 + 10 = 5
In the third case, he will do nothing and earn nothing. profit = 0

7.资源

2018中国大学生程序设计竞赛 - 网络选拔赛

题意

给你接下来n天的交易价格，每天可以(三选一)：

1.买进一个

2.卖出一个

3.什么都不做

问n天之后能获得的最大利润，并要求交易次数最少，假设一开始什么都没有，但是钱足够多。

题解

主要是加了一个最少交易次数的限制。

思考一个问题，怎么才能获得收益？

当然是低价买入高价卖出，但是如果现在卖出了，后面可能会有更高的价格可以卖出。怎么解决这个问题呢？

答：我们可以用一个优先队列（从小到大排序）代表当前所持有的所有股票，

枚举每个时候的股票价格，如果队首元素值小于当前枚举值，那么就可以卖出股票赚取利润，队首元素出队。

但是注意需要把当前枚举值再次加入队列，因为被弹出的队首元素可能会和后面价格更高股票交易获取更多的利润。

可以用当前枚举值与后面价格更多的股票交易，相当于当前枚举的股票没有进行操作.

A买入B卖出，B买入C卖出等价于A买入C卖出，相当于B没有操作。比如2 5 9，5-2=3+ 9-5=4= 9+5-(5-2)=7。

注意：那么怎么才能交易次数最少呢，当然是在后面获取更大的利润时才算交易，使用一个标记数组，对当前交易的价格进行记录，如果队首元素被标记过，那么在后面获取更大的利润时交易次数就减一，相当于之前的交易没有进行。

完整代码1：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
typedef long long ll;
using namespace std;

int main()
{
    int T, n;
    ll x, ans1, ans2;
    multiset <ll> S;
    map <int, int> mp;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        ans1 = ans2 = 0;
        S.clear();
        mp.clear();
        for (int i = 0; i < n; ++i)
        {
            scanf("%lld", &x);
            S.insert(x);
            if (*S.begin() < x) // 队首元素小于当前价格
            {
                ans2++;
                if (mp[*S.begin()] > 0) // 如果之前交易过次数减1
                {
                    ans2--;
                    mp[*S.begin()]--;
                }
                ans1 += (x - * S.begin()); // 利润
                S.erase(S.begin()); // 卖出
                S.insert(x); // 再次加入，后面可能还有更高的利润
                mp[x]++; // 标记
            }
        }
        printf("%lld %lld\n", ans1, 2 * ans2);
    }
    return 0;
}

完整代码2(multiset)：

#include <iostream>
#include <set>
using namespace std;
int T,n;
long long x,ans1,ans2;
int main(){
    multiset <pair<long long, int> > S; // 定义集合(两个数据类型为一组) 
    scanf("%lld",&T); 
    while (T--){
        scanf("%d",&n);
        ans1 = ans2 = 0;
        S.clear(); // 清空集合 
        for (int i = 0; i < n; ++i){
            scanf("%lld",&x);
            S.insert(make_pair(x, 0)); // 买入状态
            S.insert(make_pair(x, 1)); // 卖出状态
            ans1 += (x - S.begin()->first);
            if (S.begin()->second == 1) // 卖出时操作*2
                ans2 += 2;
            S.erase(S.begin()); // 删除头部元素 
        }
		printf("%lld %lld\n",ans1,ans2);
    }
}

注意：//此题需要用printf,其实putchar更快，但如果用cin,cout会超时。

END：AC...