翻车笔记 ZROI336. [18 提高 4]天 [清奇脑回路, 翻车]

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

懵逼的 题目

淦

扯淡的 题解

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

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

扫描的时候:

• 用一个小根堆堆维护[当前还未买的点中最优的买入天] (注意, 堆中的元素可以是某个要卖的天)
• 用一个multiset维护[当前最优的卖出天]
• 如果当前最优的买入天价格比这一天的价格还高, 直接把这一天push进堆
• 否则把这一天insert到multiset, 更新答案 += 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