题解 P11328

题意：

有一些徽章，想要获得一个徽章必须等级不超过某一个值，获得一个徽章会提升一定的等级，问最多获得多少个徽章。

思路：

板题的反悔贪心，把徽章按照

X_i+L_i

的获得后最高等级排序。

维护一个大根堆，从大到小给所有徽章按等级数排序。然后顺序遍历所有徽章，如果当前徽章本身就可以获得，直接加入大根堆。如果当前徽章不能获得，将它和堆里最大的数进行比较。如果它比堆里最大的徽章等级数少，而且将堆里最大的徽章等级数量去掉后可以获得当前的徽章，那就可以直接将堆里最大的值抛掉，新的徽章压入堆。

最终结果即为堆的大小。

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

O(Tn\log n)

。

注意开 long long。

代码如下：

CPP

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5e5+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",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i].t);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i].s);
	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

相关推荐

评论

题解 P11328