题解 P11457

题意：

有一些必须不间断做的工作，有最晚起始时间和消耗时间长度，问最多可以完成多少工作。

思路：

赛时把工作直接按照起始时间排序，原地趋势。

板题的反悔贪心，把工作按照最晚结束时间排序。

维护一个大根堆，从大到小给所做的所有工作按时间长短排序。然后顺序遍历所有工作，如果当前工作可以做，就加入大根堆。如果当前工作不能做，将它和堆里最大的数进行比较。如果它比堆里最大的工作时间短，而且将堆里最大的工作时间去掉后可以做当前的工作，那就可以直接将堆里最大的值抛掉，新的工作时间压入堆。

最终结果即为堆的大小。

可以证明上述方法正确，在需要更换堆中元素时总时长不减，同时工作数只会单调递增。时间复杂度

O(Tn\log n)

。

注意开 long long 以及多测清空堆。

代码如下：

CPP

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+5;
int T,n;
struct JOB{long long s,t;}a[N];
bool operator<(JOB x,JOB y){return x.t==y.t?x.s<y.s:x.t<y.t;}
bool cmp(JOB x,JOB y){return x.s+x.t<y.s+y.t;}
priority_queue<JOB,vector<JOB>,less<JOB> >q;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].s,&a[i].t);
		while(!q.empty())q.pop();
		sort(a+1,a+n+1,cmp);
		long long curt=0;
		for(int i=1;i<=n;i++){
			if(curt<=a[i].s){
				q.push(a[i]);
				curt+=a[i].t;
			}
			else{
				JOB u=q.top();
				if(a[i].t<u.t&&curt-u.t<=a[i].s){
					q.pop();
					curt-=u.t;
					q.push(a[i]);
					curt+=a[i].t;
				}
			}
		}
		printf("%d\n",q.size());
	}
	return 0;
}

文章操作

题意：

思路：

代码如下：

THE END

相关推荐

评论

题解 P11457