zoj1731(优先队列)

原文转载至:http://blog.csdn.net/fenrir1205/article/details/8275011

#include <iostream>  
#include <cstdio>  
#include <queue>  
#include <cstring>  
using namespace std;  
  
struct Schedule  
{  
    int profit;  
    int dt;  
    //先处理高利润的  
    bool operator<(const Schedule &rhs)const {  
        return profit<rhs.profit;  
  
    }  
};  
  
bool used[10001];  
priority_queue<Schedule> que;  
  
int main()  
{  
    int n;  
    while(scanf("%d",&n)!=EOF){  
        while(!que.empty())que.pop();  
        int max = 0;  
        for (int i=0;i<n;i++){  
            Schedule prod;  
            scanf("%d %d",&prod.profit,&prod.dt);  
            if (prod.dt>max) max = prod.dt;  
            que.push(prod);  
        }  
        memset(used,false,sizeof(bool)*(max+1));  
        long long sum =0;  
        int current = 0;  
        //从前面往后面去检查，对于每一个products，从其deadtime开始往前寻找没有被标记过的时间点直至时间0点或者找到没有被标记的，然后标记，并把这个profit加起来。  
        while(!que.empty()){  
            Schedule prod = que.top();  
            que.pop();  
            while(prod.dt--){  
                if (!used[prod.dt]){  
                    used[prod.dt] = true;  
                    sum+=prod.profit;  
                    break;  
                }  
            }  
        }  
        printf("%d\n",sum);  
    }  
    return 0;  
}