【题目描述：】
这些花都很漂亮，每朵花有一个美丽值W，价格为C。
小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：
操作 含义
1 W C 添加一朵美丽值为W，价格为C的花。
3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。
2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。
-1 完成添加与删除，开始包装花束
若删除操作时没有花，则跳过删除操作。
如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。
请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。
【输入格式：】
若干行，每行一个操作，以-1结束。
【输出格式：】
一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。
/*
输入样例#1：
1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1
输出样例#1：
8 5
*/
输入输出样例
【算法分析：】
方法一：红黑树.
手写红黑树是不可能的，但是可以用stl里的map水（set好像也可以不过应该比map慢一些）
map里的key-value其实就是pair，而且map里的元素是有序的：
默认按key从小到大排，所以求c的最值时应把make_pair(c, w)加入map
所以删除最小的元素就是删除map中的第一个元素，删除最大的元素就是删除map中的最后一个。
删除操作可以通过erase(iterator)来实现，定义一个map<int, int> a，
则第一个元素的位置为a.begin()
最后一个元素的位置就是 --a.end()
最后累加的时候通过迭代器遍历map，用a->first和a->second访问key, value的值
去重的话加一个bool数组去重就好
//P2073 送花
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#define mkp make_pair
#define fi first
#define se second
using namespace std; const int MAXN = + ; map<int, int> a;
bool vis[MAXN]; int main() {
int fl, w, c;
while(scanf("%d", &fl) == && fl != -) {
if(fl == ) {
scanf("%d%d", &w, &c);
if(vis[c]) continue;
a.insert(mkp(c, w));
vis[c] = ;
}
if(fl == ) {
if(!a.size()) continue;
map<int, int>::iterator it;
it = a.end();
--it; vis[it->fi] = ;
a.erase(it);
}
if(fl == ) {
if(!a.size()) continue;
map<int, int>::iterator it;
it = a.begin();
vis[it->fi] = ;
a.erase(it);
}
}
long long sum1 = , sum2 = ;
map<int, int>::iterator it;
for(it=a.begin(); it!=a.end();++it)
sum1 += it->se, sum2 += it->fi;
printf("%lld %lld\n", sum1, sum2);
}
map实现
方法二：堆
要求最大值和最小值并删除，很容易想到通过堆来实现
开一个小根堆p1和一个大根堆p2，
vis[c]表示价格为c的花的美丽度，vis[c]=0表示没有这朵花
每次读入把c分别push进两个堆里，记录vis[c]
两个变量sum1, sum2分别累加c和w，
在删除的时候sum1, sum2要分别减去c和vis[c]
//P2073 送花
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std; const int MAXN = + ; int vis[MAXN];
priority_queue<int, vector<int>, greater<int> > q1;
priority_queue<int> q2; int main() {
int fl, w, c;
long long sum1 = , sum2 = ;
while(scanf("%d", &fl) == && fl != -) {
if(fl == ) {
scanf("%d%d", &w, &c);
if(vis[c]) continue;
q1.push(c), q2.push(c);
vis[c] = w;
sum1 += w, sum2 += c;
}
if(fl == ) {
while(!q2.empty() && !vis[q2.top()]) q2.pop();
if(q2.empty()) continue;
int t = q2.top();
sum1 -= vis[t];
sum2 -= t;
vis[t] = ;
q2.pop();
}
if(fl == ) {
while(!q1.empty() && !vis[q1.top()]) q1.pop();
if(q1.empty()) continue;
int t = q1.top();
sum1 -= vis[t];
sum2 -= t;
vis[t] = ;
q1.pop();
}
}
printf("%lld %lld\n", sum1, sum2);
}
堆实现