題目背景

小明準備給小紅送一束花，以表達他對小紅的愛意。他在花店看中了一些花，準備用它們包成花束。

題目描述

這些花都很漂亮，每朵花有一個美麗值W，價格為C。

小明一開始有一個空的花束，他不斷地向里面添加花。他有以下幾種操作：

操作 含義

1 W C 添加一朵美麗值為W，價格為C的花。

3 小明覺得當前花束中最便宜的一朵花太廉價，不適合送給小紅，所以刪除最便宜的一朵花。

2 小明覺得當前花束中最貴的一朵花太貴，他心疼自己的錢，所以刪除最貴的一朵花。

-1 完成添加與刪除，開始包裝花束

若刪除操作時沒有花，則跳過刪除操作。

如果加入的花朵價格已經(jīng)與花束中已有花朵價格重復，則這一朵花不能加入花束。

請你幫小明寫一個程序，計算出開始包裝花束時，花束中所有花的美麗值的總和，以及小明需要為花束付出的總價格。

輸入輸出格式

輸入格式：

?

若干行，每行一個操作，以-1結束。

?

輸出格式：

?

一行，兩個空格隔開的正整數(shù)表示開始包裝花束時，花束中所有花的美麗值的總和。以及小明需要為花束付出的總價格。

?

輸入輸出樣例

輸入樣例#1：
1 1 1 1 2 5 2 1 3 3 3 1 5 2 -1 輸出樣例#1：
8 5

說明

對于20%數(shù)據(jù)，操作數(shù)<=100，1<=W,C<=1000。

對于全部數(shù)據(jù)，操作數(shù)<=100000,1<=W,C<=1000000。

分析：我們要維護當前隊列的最小值和最大值，但一旦刪除某個數(shù)字時，我們的最大最小值就無法維護，所以我們要使隊列有序，但不斷排序的話肯定會超時，所以用set優(yōu)化。 代碼： #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

?

轉載于:https://www.cnblogs.com/harden/p/5797050.html

總結

以上是生活随笔為你收集整理的送花（洛谷 2073）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。