【题解】建筑抢修

[JSOI2007]建筑抢修

https://ac.nowcoder.com/acm/problem/20154

感想:
这个题跟很早以前入门贪心的题看电影很类似,但是那个题是给定了开始时间和结束时间,所以按照结束时间贪心就好了,这个题给出的是持续时间和结束时间,但是依然是一个贪心。

思路:
如果按照工作时间排序,尽量做时间短的不一定就是最优解,因为可能时间短的都截止的晚,导致你截止时间早的就完不成了。
所以首先肯定是先要按照结束时间排序,因为前面的工作要先干完才能干后面的,这很容易想到。
然后,贪心肯定是能干就干,先把已经干了活的总时间和加起来。但是会遇到这样一个问题,就是之后某一个活就不够时间干了。因此可以发现,在保证干活数一定的情况下,尽量让这个总时间小一点比较好。
因此可以得到思路:先对结束时间从小到大排序,然后扫一遍总工程,能干就干,记录下总时长和答案,同时把这个工程自己的持续时间放到一个优先队列里面;如果发现一个工程干不了了,可以看看优先队列里面的最大时长的工作是不是比现在的还大,是的话就可以把那个换成这个,并且要保证你换完了就可以工作了(有可能截止时间太小,你换完了也不能工作),这样就可以把总时间减小了。

代码:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=5e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

struct Node{
    ll t,end;
}node[maxn];

int cmp(Node a,Node b){
    return a.end<b.end;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld %lld",&node[i].t,&node[i].end);
    }
    sort(node+1,node+1+n,cmp);
    priority_queue<ll> q;
    ll tot=0,ans=0;
    for(int i=1;i<=n;i++){
        if(tot+node[i].t<=node[i].end){
            ans++;
            tot+=node[i].t;
            q.push(node[i].t);
        }
        else if(q.top()>node[i].t&&tot-q.top()+node[i].t<=node[i].end){
            tot-=q.top();
            q.pop();
            tot+=node[i].t;
            q.push(node[i].t);
        }
    }
    printf("%lld\n",ans);
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
我见java多妩媚:大外包
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务