原题链接 https://www.luogu.com.cn/problem/P2073
题解
团队作业中【平衡树应用】的一道题目，但读完题目后觉得可以直接模拟，不用平衡树做；
题目中只有一种添加操作和两种删除操作，而且两种删除操作是分别删除一个最大值或最小值，那么我们很快就可以想到可以用两个堆（大根堆和小根堆）来分别维护最大值和最小值；
每次删除一个最大值或最小值时，我们就取大根堆或小根堆的堆顶将其删除就好，至于怎么判断一种花有没有被删除，我们可以将其美丽值赋为 $0$ 就好了；
还有就是注意到了题目中说道 “ 如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。”，也就是说一个价格对应了一个美丽值，所以我们可以开一个数组：$v [ i ]$ 来表示价格为 i 的花束对应的美丽值是多少；
剩下需要注意的细节代码中有注释：
$Code$：
#include <bits/stdc++.h> #define maxn 1000001 using namespace std; int v[maxn]; //v[i]：价格为i的话美丽值是多少 long long beauty,value; priority_queue<int,vector<int>,less<int> > qmin; //小根堆 priority_queue<int,vector<int>,greater<int> >qmax; //大根堆 void Add() //添加一朵花 { int x,y; cin>>x>>y; //美丽值为x,价格为y if (v[y]) return; //重复价格的花束不能添加 qmin.push(y); //注意是将价格y入堆 qmax.push(y); v[y]=x; beauty+=x,value+=y; //直接算出现有花束的美丽值和价格的总和,方便询问时直接输出 } void Delin() //删除一个价格最小的花束 { while(!qmin.empty()&&v[qmin.top()]==0) qmin.pop(); //注意要先将已经删除了的花束(美丽值为0)弹出堆 if (!qmin.empty()) { int now=qmin.top(); //now记录价格最小的花束的价格 beauty-=v[now]; //更新总美丽值 value-=now; //更新总价格 v[now]=0; //将其删除,美丽值设为0 qmin.pop(); //弹出now } } void Delax() //删除一个价格最大的花束 { while(!qmax.empty()&&v[qmax.top()]==0) qmax.pop(); //注意要先将已经删除了的花束(美丽值为0)弹出堆 if (!qmax.empty()) { int now=qmax.top(); //now记录价格最小的花束的价格 beauty-=v[now]; //更新总美丽值 value-=now; //更新总价格 v[now]=0; //将其删除,美丽值设为0 qmax.pop(); //弹出now } } int main() { int q; cin>>q; while(q!=-1) { if (q==1) Add(); if (q==2) Delin(); if (q==3) Delax(); cin>>q; } cout<<beauty<<" "<<value; return 0; }