【题解】建筑抢修
[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; }