poj 1456 Supermarket（贪心+优先队列）

题意：有N件商品，分别给出商品的价值和销售的最后期限，只要在最后日期之前销售处，就能得到相应的利润，并且销售该商品需要1天时间。

问销售的最大利润。

这题很容易想到贪心但是贪心方向不用，复杂度也是不同的。

我第一次想到的贪心是将商品按照权值从大到小排序然后再一次安排如果当前日期已经被占用那么就向前面的日期退移。

但是这种方法很难想到优化的方法而且复杂度有点高最坏的情况因该有n*n但是数据比较水还是能过的。

第二种方法是先讲商品按照最后期限从大到小排，然后只要for一遍日期，过程中利用优先队列存入这日期之前的商品并且每次

pop一个，毕竟1天卖一个。

#include <iostream>

#include <cstring>

#include <queue>

#include <vector>

#include <cstdio>

using namespace std;

const int M = 1e4 + 10;

int n , sum;

struct line {

    int val;

    line(int val):val(val) {}

    bool operator <(const line &a) const {

        return val < a.val;

    }

};

struct TnT {

    int val , deadline;

}T[M];

bool cmp(TnT a , TnT b) {

    return a.deadline > b.deadline;

}

void solve() {

    priority_queue<line>q;

    int j = 1;

    for(int i = T[1].deadline ; i >= 1 ; i--) {

        for( ; j <= n && T[j].deadline >= i ; j++) {

            q.push(line(T[j].val));

        }

        if(!q.empty()) {

            line gg = q.top();

            q.pop();            sum += gg.val;

        }

    }

}

int main() {

    while(scanf("%d" , &n) != EOF) {

        for(int i = 1 ; i <= n ; i++) {

            scanf("%d%d" , &T[i].val , &T[i].deadline);

        }

        sort(T + 1 , T + n + 1 , cmp);

        sum = 0;

        solve();

        printf("%d\n" , sum);

    }

    return 0;

}

巴特西

poj 1456 Supermarket（贪心+优先队列）

最新文章

热门文章