poj1456_Supermarket(最小堆)

题目
思路:

  • 题目给的是时间$t_i$ 意思是:距离过期的时间,只要 $[1,t_i]$ 之内被卖出就行了
  1. 将时间从小到大排序,维护一个小根堆,
  2. 堆为空,加入,
  3. 当不为空时,如果 $t_i$ > que.size() 意思是当前物品距离过期的时间大于已经卖出的个数,那么该物品一定可以卖出
  4. 如果 $t_i$ = que.size(),判断堆顶的卖出的最小利润是否小于该物品利润,小于就换成该物品,
  5. 用一个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 协议 ,转载请注明出处!