建筑抢修 BZOJ 1029

建筑抢修

【问题描述】

小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

【输入格式】

第一行是一个整数N接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。

【输出格式】

输出一个整数S，表示最多可以抢修S个建筑.

【样例输入】

4
100 200
200 1300
1000 1250
2000 3200

【样例输出】

【数据范围】

N < 150,000，T1 < T2 < maxlongint

题解：

先按T2排序，按顺序枚举

贪心考虑，如果能在T2内维修好就加入左偏树（大根堆）

否则考虑与堆顶的关系

如果不维修堆顶而维修当前建筑使用时间更少，就将堆顶弹出加入当前建筑

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 inline int Get()

 {

     int x;

     char c;

     while((c = getchar()) < '' || c > '');

     x = c - '';

     while((c = getchar()) >= '' && c <= '') x = x *  + c - '';

     return x;

 }

 const int me = ;

 struct building

 {

     int x, y;

 }a[me];

 int n, rt, num;

 int dis[me], lc[me], rc[me];

 inline bool rule(const building &a, const building &b)

 {

     if(a.y != b.y) return a.y < b.y;

     return a.x < b.x;

 }

 int Marge(int x, int y)

 {

     if(!x) return y;

     if(!y) return x;

     if(a[x].x < a[y].x) swap(x, y);

     rc[x] = Marge(rc[x], y);

     if(dis[lc[x]] < dis[rc[x]]) swap(lc[x], rc[x]);

     if(!rc[x]) dis[x] = ;

     else dis[x] = dis[rc[x]] + ;

     return x;

 }

 int main()

 {

     n = Get();

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

     {

         a[i].x = Get();

         a[i].y = Get();

     }

     sort(a + , a +  + n, rule);

     int ti = ;

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

     {

         if(ti + a[i].x <= a[i].y)

         {

             rt = Marge(rt, i);

             ti += a[i].x;

             ++num;

         }

         else

         {

             if(!rt) continue;

             int c = ti - a[rt].x + a[i].x;

             if(c <= a[i].y && a[i].x < a[rt].x)

             {

                 int a = lc[rt], b = rc[rt];

                 rt = Marge(a, b);

                 rt = Marge(rt, i);

                 ti = c;

             }

         }

     }

     printf("%d", num);

 }

巴特西