P2073 送花

这是一道模拟题

题目背景

小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。

题目描述

这些花都很漂亮，每朵花有一个美丽值 $W$，价格为 $C$。

小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：

  • $1\ W\ C$：添加一朵美丽值为 $W$，价格为 $C$ 的花。

如果此时花束中已经有了相等价格的花，那么这朵花不能加入花束。

  • $2$：删除当前花束里最贵的一朵花。
  • $3$：删除当前花束里最便宜的一朵花。
  • $-1$：完成添加与删除，开始包装花束。

当花束为空时，忽略操作 $2$ 和 $3$。

请你写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。

输入以 $-1$ 结束。记总操作数为 $m$ 。

对于全部数据，$m \le 10^5$，$1\le W,C\le 10^6$。

分析

01-暴力

维护一个序列，每次操作都遍历模拟解决，显然不行。

02-性质

发现本质上维护的是一个“花束”。
注意到花束内部并没有顺序之分，联想到集合set。

03-正解

想到这一点，这道题就变成了模拟题。
主要考察对STL::set的运用

04-实现

依题意模拟即可

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
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int w, c, op;

long long ans1, ans2;

struct node{
	int w, c;
	bool operator < (const node &a) const {
		return c < a.c;
	}
};

set<node> s;

signed main(){
	
	while(scanf("%d", &op) == 1 && op != -1){
		if (op == 1){
			scanf("%d%d", &w, &c);
			node t = {w, c};
			s.insert(t);
		}
		
		if (op == 2){
			if (s.size())
				s.erase(--s.end());
		}
		
		if (op == 3){
			if (s.size())
				s.erase(s.begin());
		}
	}
	
	for (auto it : s)
		ans1 += it.c,
		ans2 += it.w;
	
	swap(ans1, ans2);
	cout << ans1 << " " << ans2;
	
	return 0;
}

set in OI-Wiki

Written with StackEdit中文版.