先按照时间排序，维护一个堆，然后贪心
1
#include <stdio.h>
2#include <queue>
3#include <algorithm>
4#include <vector>
5using namespace std;
6class node
7
{
8
public:
9 int p;
10 int t;
11
node(int _p,int _t):p(_p),t(_t){}
12
};
13class cmp
14{
15 public:
16 bool operator () (const node &a,const node &b) const
17 {
18 return a.t<b.t;
19
}
20};
21priority_queue<int,vector<int>,greater<int> > q;
22vector<node> l;
23int n;
24int main()
25{
26 while(scanf("%d",&n)!=EOF)
27 {
28 int p,t;
29 l.clear();
30 for(int i=0;i<n;i++)
31 {
32 scanf("%d %d",&p,&t);
33 l.push_back(node(p,t));
34 }
35 p=0;
36 t=0;
37 int sum=0;
38 sort(l.begin(),l.end(),cmp());
39 while(!q.empty()) q.pop();
40 for(int i=0;i<n;i++)
41 {
42 t+=l[i].t-p;
43 if(t==0)
44 {
45 if(q.empty()) continue;
46 else
47 {
48 if(l[i].p>q.top())
49 {
50 sum+=l[i].p-q.top();
51 q.pop();
52 q.push(l[i].p);
53 }
54 }
55 }
56 else
57 {
58 t--;
59 sum+=l[i].p;
60 q.push(l[i].p);
61 }
62 p=l[i].t;
63 }
64 printf("%d\n",sum);
65 }
66 return 0;
67}
68
69
posted on 2011-02-13 16:59
avcpp 阅读(47)
评论(0) 编辑 收藏 引用