【贪心+堆】XMU 1584 小明的烦恼

题目链接：

　　http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1584

题目大意：

　　给n(n<=100 000)个任务的耗时和截至时间，问最少不能完成几个任务。

题目思路：

　　【贪心+堆】

　　一开始想贪心但是没想到要加个堆，又跪了。

　　首先按照结束时间排序，结束时间早的肯定优先考虑。

　　如果当前的任务无法完成，就将当前任务和之前已经做了的任务中耗时最长的取消掉，改做当前任务

　　（如果当前任务就是耗时最长的则不用加当前任务，因为取消一个换另一个结果不会更差，只会使已经消耗的时间减少）

　　所以用一个最大堆记录当前的最大耗时。

  1 //
  2 //by coolxxx
  3 //
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<string>
  7 #include<iomanip>
  8 #include<memory.h>
  9 #include<time.h>
 10 #include<stdio.h>
 11 #include<stdlib.h>
 12 #include<string.h>
 13 #include<stdbool.h>
 14 #include<math.h>
 15 #define min(a,b) ((a)<(b)?(a):(b))
 16 #define max(a,b) ((a)>(b)?(a):(b))
 17 #define abs(a) ((a)>0?(a):(-(a)))
 18 #define lowbit(a) (a&(-a))
 19 #define sqr(a) ((a)*(a))
 20 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
 21 #define eps 1e-8
 22 #define J 10
 23 #define MAX 0x7f7f7f7f
 24 #define PI 3.1415926535897
 25 #define N 100004
 26 using namespace std;
 27 int n,m,lll,ans,cas;
 28 struct xxx
 29 {
 30     int c,e;
 31 }a[N];
 32 int h[N];
 33 void weihuup(int h[],int x)
 34 {
 35     int xx=x>>1;
 36     if(!xx)return;
 37     if(h[x]>h[xx])
 38     {
 39         swap(h[x],h[xx]);
 40         weihuup(h,xx);
 41     }
 42 }
 43 void weihudown(int h[],int x)
 44 {
 45     int xx=x+x,yy=x+x+1,zz;
 46     if(xx>h[0])return;
 47     if(yy<=h[0])
 48     {
 49         zz=h[xx]>h[yy]?xx:yy;
 50         if(h[x]<h[zz])
 51         {
 52             swap(h[x],h[zz]);
 53             weihudown(h,zz);
 54         }
 55     }
 56     else
 57     {
 58         if(h[x]<h[xx])
 59             swap(h[x],h[xx]);
 60     }
 61 }
 62 bool cmp(xxx aa,xxx bb)
 63 {
 64     if(aa.e!=bb.e)return aa.e<bb.e;
 65     return aa.c<bb.c;
 66 }
 67 int main()
 68 {
 69     #ifndef ONLINE_JUDGE
 70 //    freopen("1.txt","r",stdin);
 71 //    freopen("2.txt","w",stdout);
 72     #endif
 73     int i,j,k;
 74 //    while(~scanf("%s",s1))
 75     while(~scanf("%d",&n))
 76     {
 77         for(i=1;i<=n;i++)
 78         {
 79             scanf("%d%d",&a[i].c,&a[i].e);
 80         }
 81         sort(a+1,a+1+n,cmp);
 82         for(i=1,k=0;i<=n;i++)
 83         {
 84             if(k+a[i].c<=a[i].e)
 85             {
 86                 h[++h[0]]=a[i].c;
 87                 weihuup(h,h[0]);
 88                 k+=a[i].c;
 89             }
 90             else
 91             {
 92                 if(a[i].c>h[1])continue;
 93                 k=k-h[1]+a[i].c;
 94                 h[1]=a[i].c;
 95                 weihudown(h,1);
 96             }
 97         }
 98         printf("%d
",n-h[0]);
 99     }
100     return 0;
101 }
102 
103 
104 /*
105 //
106 
107 //
108 */

View Code