poj1456_Supermarket(最小堆)
题目
思路:
- 题目给的是时间$t_i$ 意思是:距离过期的时间,只要 $[1,t_i]$ 之内被卖出就行了
- 将时间从小到大排序,维护一个小根堆,
- 堆为空,加入,
- 当不为空时,如果 $t_i$
>
que.size()
意思是当前物品距离过期的时间大于已经卖出的个数,那么该物品一定可以卖出 - 如果 $t_i$
=
que.size()
,判断堆顶的卖出的最小利润是否小于该物品利润,小于就换成该物品, - 用一个ans记录利润
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
int pro;
int day;
bool operator<(const node& t) const {
return this->day>t.day;
}
};
int main() {
// freopen("a.txt","r",stdin);
int n;
while ( scanf("%d",&n) != EOF ) {
priority_queue<int> que;
vector<node> num;
for (int i=1;i<=n;i++) {
node temp;
scanf("%d %d",&temp.pro,&temp.day);
num.push_back(temp);
}
sort(num.begin(),num.end());
// for (int i=0;i<n;i++) {
// printf("%d %d ",num[i].pro,num[i].day);
// }
// printf("\n");
int ans=0;
for (int i=0;i<n;i++) {
if( que.empty() ) {
que.push( -num.back().pro );
ans += num.back().pro;
num.pop_back();
}
else {
if( num.back().day == que.size() ) {
if( num.back().pro > -que.top() ) { //利润大才替换小堆的堆顶
ans += que.top();
ans += num.back().pro;
que.pop();
que.push(-num.back().pro);
num.pop_back();
}
else num.pop_back();
} else if (num.back().day > que.size() ) {
ans += num.back().pro;
que.push(-num.back().pro);
num.pop_back();
}
}
}
printf("%d\n",ans);
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!