题意:
给出n个建筑的修复需要的时间和截止时间,建筑必须要在截止时间结束前修复才行,问最优的修复顺序下的最大修复建筑数量是多少。
解题思路:
首先第一印象肯定是和贪心脱不了关系了,如果可以修复,我们肯定先修复截止时间早的建筑,后修复截止时间迟的建筑。所以我们首先需要对截止时间进行排序,然后从第一个到最后一个选择性的修复就行。但是我们不能直接以截止时间进行贪心,比如一个建筑截止时间早但是修复时间很大,那么就压缩了其它建筑的修复时间,因此我们需要有一种类似于反悔的策略,比如如果比如当修复到建筑i的时候,如果在此时的条件下不能修复它(也就是当前时间+修复它所需要的时间超过了他的截止时间),但是我们选择修复它能使当前时间提前,那么我们也选择修复它,因为它使得修复到i的时间戳提前了,这样就给后面的建筑提供更大的时间,就相当于从前面已经修复的建筑中去除一个修复时间最长的(就相当于反悔了),因此我们还需要一个优先队列来记录我们修复了哪几个建筑,然后贪心的修复就行。(相关细节在代码中有提)。
代码如下:
#include<bits/stdc++.h> #define LL long long #define all(x) (x).begin(),(x).end() #define le(x) ((int)(x).size()) #define pii pair<int,int> #define PII pair<LL,LL> #define mp make_pair #define pb push_back #define fi first #define se second #define db printf("Here!\n"); using namespace std; const double eps=1e-8; const double Pi=4.0*atan(1.0); const LL inf=1e14+10; const int N=2e5+5; const int M=1e6+5; const int mod=1e9+7; int n,m,k,t,T,len,op,x,y,z,ok; PII p[N]; struct node{ LL time,id; bool operator<(const node &x)const{ return time<x.time; } }; priority_queue<node>q; void solve(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld%lld",&p[i].se,&p[i].fi); sort(p+1,p+1+n);//对截止时间进行排序 LL now=p[1].se,ans=1;//记录修复ans个建筑的时间戳和答案 q.push(node{now,1}); for(int i=2;i<=n;i++){ if(p[i].se+now<=p[i].fi){//如果当前时间戳加上修复i建筑的时间小于等于i建筑的截止时间,那么答案+1 ans++; q.push(node{p[i].se,i}); now+=p[i].se;//更新时间戳 }else { if(p[i].se<q.top().time){//如果选择修复i建筑能使得时间戳提前的话就进行上面的反悔操作 now-=q.top().time; q.pop(); now+=p[i].se; q.push(node{p[i].se,i}); } } } printf("%lld\n",ans); } int main(){ //int o;scanf("%d",&o); //while(o--){ solve(); //} return 0; }