CCPC 2018网络预赛 hdu 6438 Buy and Resell

【题目链接】

题目意思

T组案例，给一个n，然后给n个数字，给出n个数字，从第一个点走到最后一个点，可以在任意一个点以ai的价格买或者卖物品，求最大利润和最大利润下的最少次数。

Sample Input
3
4
1 2 10 9
5
9 5 9 10 5
2
2 1
Sample Output
16 4
5 2
0 0

Hint
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

解题思路

CF原题？？？只不过加了一个次数？？？2018CCPC网络赛？？？
赛后才知道CF原题，赛时队友说先全买在卖，然后我觉得应该先找最大然后找最大的左边的最小的，然而讨论来讨论去，总觉得有问题，然后看到我们学校有队伍过03了，跟榜去了，赛后发现挺简单的，一发AC？？？
维护一个multiset，如果multiset中有比现在的数字小的数字就买卖一次，这里就有一个问题了，就是买卖次数可能会有重复，这时，我们需要记录一下数字出现的次数（num），数字第一次出现的次数（book），如果当前的买卖的买值 t 满足num[t]==book[t]，说明该数字都是第一次出现的，即cnt++，book[t]--，反之不进行任何操作。
一个易错点，买次进行买卖操作时，对于每一个买值，需要insert两次，因为需要让其有传递性，而且在当前位置我也可以买入，不妨以4个数字1 2 3 4为例，当遍历完后，若insert一次，set中则只有4一个元素，ans=3,cnt=2，若insert两次，set中有1 2 两个元素，ans=4,cnt=4，显然需要inset两次，让其具有传递性。

AC代码

#include <iostream>
#include <set>
#include <map>
#define ll long long
using namespace std;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        multiset<int>s;
        map<int, int>book;
        map<int, int>num;
        int n, t;
        ll ans = 0, cnt = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &t);
            if (s.size() == 0 || *s.begin() >= t)
            {
                s.insert(t);
                num[t]++;
                book[t]++;
            }
            else
            {
                if (book[*s.begin()] == num[*s.begin()])
                {
                    cnt++;
                    book[*s.begin()]--;
                }
                num[*s.begin()]--;
                ans += t - *s.begin();
                s.erase(s.begin());
                s.insert(t);
                s.insert(t);
                num[t] += 2;
                book[t]++;
            }
        }
        cnt *= 2;
        printf("%lld %lld\n", ans, cnt);
    }
}