当前位置: 首页 > 工具软件 > POWDER > 使用案例 >

Magic Powder - 1 CodeForces - 670D1(优先队列进一步理解)

冯胤
2023-12-01

写这个题的时候一直在想怎么才能动态排序(一遍改变数值,一遍从新改变相应的顺序),到最后才突然想起来这不就是优先队列吗,通过这题对优先队列的动态排序有了进一步理解。好题!

AC代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1e6+5;
struct node{
	int need,has;
	bool operator<(const node&a)const{
	 return (a.has/a.need)<(has/need);
	}
}x[maxn];
priority_queue<node>q;
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>x[i].need;
	for(int i=1;i<=n;i++)cin>>x[i].has;
	for(int i=1;i<=n;i++)q.push(x[i]);
    while(k){
    	node temp=q.top();
    	q.pop();
    	temp.has++;
    	k--;
    	q.push(temp);
	}
	int ans=q.top().has/q.top().need;
	cout<<ans<<endl;
}

 

 类似资料: