送花（洛谷 2073）

题目背景

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

题目描述

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

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

操作含义

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

3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。

2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。

-1 完成添加与删除，开始包装花束

若删除操作时没有花，则跳过删除操作。

如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。

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

输入输出格式

输入格式：

若干行，每行一个操作，以-1结束。

输出格式：

一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。

输入输出样例

输入样例#1：

输出样例#1：

8 5

说明

对于20%数据，操作数<=100，1<=W,C<=1000。

对于全部数据，操作数<=100000,1<=W,C<=1000000。

分析：我们要维护当前队列的最小值和最大值，但一旦删除某个数字时，我们的最大最小值就无法维护，所以我们要使队列有序，但不断排序的话肯定会超时，所以用set优化。
代码：
#include<cstdio>
#include<iostream>
#include<set>
#define M 1000010
using namespace std;
set<int> q;
int bea[M],sum_m,sum_v;
int read()
{
    char c=getchar();int num=0,flag=1;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
    return num*flag;
}
int main()
{
    set<int>::iterator it;
    while(1)
    {
        int f=read();
        if(f==-1)break;
        if(f==1)
        {
            int mei=read(),val=read();
            if(bea[val])continue;
            else
            {
                bea[val]=mei;
                q.insert(val);
                sum_m+=mei;sum_v+=val;
            }
        }
        else if(f==2&&!q.empty())
        {
            it=q.end();it--;
            sum_m-=bea[*it];sum_v-=*it;
            q.erase(it);bea[*it]=0;
        }
        else if(!q.empty())
        {
            it=q.begin();
            sum_m-=bea[*it];sum_v-=*it;
            q.erase(it);bea[*it]=0;
        }
    }
    printf("%d %d",sum_m,sum_v);
    return 0;
}

View Code