题目背景
小明准备给小红送一束花,以表达他对小红的爱意。他在花店看中了一些花,准备用它们包成花束。
题目描述
这些花都很漂亮,每朵花有一个美丽值W,价格为C。
小明一开始有一个空的花束,他不断地向里面添加花。他有以下几种操作:
操作含义
1 W C 添加一朵美丽值为W,价格为C的花。
3 小明觉得当前花束中最便宜的一朵花太廉价,不适合送给小红,所以删除最便宜的一朵花。
2 小明觉得当前花束中最贵的一朵花太贵,他心疼自己的钱,所以删除最贵的一朵花。
-1 完成添加与删除,开始包装花束
若删除操作时没有花,则跳过删除操作。
如果加入的花朵价格已经与花束中已有花朵价格重复,则这一朵花不能加入花束。
请你帮小明写一个程序,计算出开始包装花束时,花束中所有花的美丽值的总和,以及小明需要为花束付出的总价格。
输入格式:
若干行,每行一个操作,以-1结束。
输出格式:
一行,两个空格隔开的正整数表示开始包装花束时,花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。
输入样例
1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1
输出样例
8 5
说明
对于20%数据,操作数<=100,1<=W,C<=1000。
对于全部数据,操作数<=100000,1<=W,C<=1000000。
其实挺裸的
唯一的坑点—–为什么题目要把操作序号反着写啊啊啊啊啊啊啊(掀桌)
总之具体解释见注释吧
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int read()
{
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}
void print(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9)print(x/10);
putchar(x%10+'0');
}
struct node
{
node* ch[2];
int w,r,c;
node(int w,int c) :w(w),c(c) {r=rand();ch[0]=ch[1]=NULL;}
int cmp(int x){if(c==x)return -1;return x<c ?0:1;}
};
node* rt=NULL;
int sumw,sumc;
int w,c;
bool judge[1000010];
void rotate(node* &p,int d)
{
node* k=p->ch[d^1];
p->ch[d^1]=k->ch[d];
k->ch[d]=p;
p=k;
}
void ins(node* &p,int x)
{
if(p==NULL){p=new node(w,c);return;}
int d=p->cmp(x);
ins(p->ch[d],x);
if(p->ch[d]->r < p->r)rotate(p,d^1);
}
void del(node* &p,int d)
{
if(p==NULL) return;
if(p->ch[d]!=NULL){del(p->ch[d],d);return;}
//左/右孩子不为空,说明还有更小/大的,继续向下寻找
else
{
//左/右孩子为空,开始删除,要再删除前对总美丽值&价格更新
sumw-=p->w; sumc-=p->c; judge[p->c]=false;
node* k=p; p=p->ch[d^1]; delete(k);
return ;
}
}
int main()
{
while(1)
{
int k=read();
if(k==-1) break;
if(k==1)
{
w=read();c=read();
if(judge[c])continue;//记得重复价格不放
ins(rt,c);
judge[c]=true;
sumw+=w; sumc+=c;
}
else if(k==2) del(rt,1);//删除最大就找最右的孩子
else if(k==3) del(rt,0); //删除最小反之
}
print(sumw);printf(" ");print(sumc);
return 0;
}