首页 > 代码库 > BZOJ 1029 建筑抢修（贪心堆）

BZOJ 1029 建筑抢修（贪心堆）

2024-10-30 04:26:01   211人阅读

原题代号：BZOJ 1029

原题描述：

建筑抢修

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

Input

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

Output

　　输出一个整数S，表示最多可以抢修S个建筑.N < 150,000;  T1 < T2 < maxlongint

Sample Input

4
100 200
200 1300
1000 1250
2000 3200

Sample Output

3
先按第二个时间对所有的建筑排个序，然后直接贪心是不行的，所以需要用到优先队列，如果能直接抢修的就抢修，同时将t1的值保存在优先队列中（因为优先队列默认大数在顶部）
如果碰到抢修时间不够的建筑，判断一下优先对列顶部的建筑物抢修时间是否大于这个时间不够的抢修时间，如果大于则进行替换，这样能留出更多的时间得到最优解
AC代码：
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <iostream>
# include <fstream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <math.h>
# include <algorithm>
using namespace std;
# define pi acos(-1.0)
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define For(i,n,a) for(int i=n; i>=a; --i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define Fo(i,n,a) for(int i=n; i>a ;--i)
typedef long long LL;
typedef unsigned long long ULL;

struct construction
{
    int t1,t2;
} a[150005];

bool cmp(construction a,construction b)
{
    return a.t2<b.t2;
}

int sum,num;
priority_queue<int>Q;

int main()
{
    int sum=0,num=0;
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].t1>>a[i].t2;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1; i<=n; i++)
    {
        if(a[i].t1<=a[i].t2-sum)
        {
            Q.push(a[i].t1),sum+=a[i].t1,num++;
        }
        else
        {
            if(num==0)continue;
            if(a[i].t1<Q.top())
            {
                sum-=Q.top()-a[i].t1;
                Q.pop();
                Q.push(a[i].t1);
            }
        }
    }
    cout<<num<<endl;
    return 0;
}

　

BZOJ 1029 建筑抢修（贪心堆）


联系
我们