bzoj1029 [JSOI2007]建筑抢修

 1 #include<cstdio>
 2 #include<queue>
 3 #include<algorithm>
 4 #define mp make_pair
 5 #define fi first
 6 #define sc second
 7 using namespace std;
 8 const int N = 2001010;
 9 priority_queue<int> Q;
10 struct g{
11     int a,b;
12 }v[N];
13 bool cmp(g u,g v)
14 {
15     if (u.b==v.b) 
16     return u.a>v.a;
17     return u.b<v.b;
18 }
19 int n,sum,i,ans;
20 int main()
21 {
22     scanf("%d",&n);
23     for (i=1;i<=n;i++)
24     scanf("%d%d",&v[i].a,&v[i].b);
25     sort(v+1,v+1+n,cmp); 
26     for (i=1;i<=n;i++)
27     {
28         //printf("%d %d\n",sum,v[i].b);
29         if (sum+v[i].a>v[i].b)
30         {
31             if ((!Q.empty())&&(Q.top()>v[i].a))
32             {
33                 sum-=Q.top();
34                 sum+=v[i].a;
35                 Q.pop();
36                 Q.push(v[i].a);
37             }
38         }
39         else
40         {
41             Q.push(v[i].a);
42             sum+=v[i].a;
43             ans++;
44         }
45     } 
46     printf("%d\n",ans);
47 }