• multiset中间没有下划线
  • multiset.size()返回的是值的种类数而非值的个数
  • multiset.erase(x)删除的是这个大小为x的所有的值, 想要删除一个可以multiset.erase(multiset.find(x))

懵逼的 题目

扯淡的 题解

DP很好想然而似乎和正解没什么关系

正解看上去就是一个可以反悔的贪心…

扫描的时候:

  • 用一个小根堆堆维护[当前还未买的点中最优的买入天] (注意, 堆中的元素可以是某个要卖的天)
  • 用一个multiset维护[当前最优的卖出天]
  • 如果当前最优的买入天价格比这一天的价格还高, 直接把这一天push进堆
  • 否则把这一天insertmultiset, 更新答案 += a[i] - q.top();
    • 如果堆顶的元素在multiset中出现过, 说明堆顶的那一天相当于三点一线的中间那个点, 舍去可以获得更少的买卖次数, 把这个点从multiset中删除
    • 否则, 说明这个点从未被用过, 把这个点从堆中删除
  • 最后买卖的次数就是multset个数的二倍

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#define LL long long
#define MAXN (50000 + 5)
#define int LL 
using namespace std;
struct cmp
{
    bool operator () (const int x, const int y)
    { return x > y; }
};
int n, a[MAXN];
void solve()
{
    priority_queue<int, vector<int>, cmp> q;
    multiset<int> sold;
    LL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!q.empty() && q.top() < a[i])
        {
            ans += a[i] - q.top();
            sold.insert(a[i]);
            if (sold.find(q.top()) != sold.end())
                sold.erase(sold.find(q.top()));
            else
                q.pop();
        }
        q.push(a[i]);
    }
    int nans = 0;
    while (!sold.empty())
        sold.erase(sold.begin()), ++nans;
    printf("%lld %lld\n", ans, nans << 1);
}
#undef int
int main()
#define int LL
{
    freopen("in.in", "r", stdin);
    freopen("wa.out", "w", stdout);
    int t;
    scanf("%lld", &t);
    while (t--)
    {
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        solve();
    }
    return 0;
}

By 联赛钦定爆零的 Cansult