tokitsukaze and Soldier


题意:
选择k个士兵,在满足总共的mins>=k的情况下,让他们的值和最大
思路:
是真的菜,这么简单的贪心都想不到,假设我们已经知道了最后选取k个士兵,那么我们可以优先选择s>=k最大的k个士兵,然后我们将士兵们排序嘛,然后按照值放进堆中,如果堆的大小大于限制,把最垃圾的t出来!
ac代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
struct node{
   
	ll x;
	ll y;
	bool operator <(const node&W)const
	{
   
		if(y!=W.y)
		return y>W.y;
		return x<W.y;
	}
}q[N];
ll dp[N];
int n;
priority_queue<ll,vector<ll>,greater<ll>>Q;
int main()
{
   
	cin >> n;
	for(int i=1;i<=n;i++)
	{
   
		cin>>q[i].x>>q[i].y;
	 } 
	 sort(q+1,q+1+n);
	 ll res=0;
	 ll ans=0;
	 for(int i=1;i<=n;i++)
	 {
   
	 	res+=q[i].x;
	 	Q.push(q[i].x);
	 	while(Q.size() && Q.size()>q[i].y)
	 	{
   
	 		auto t=Q.top();
	 		Q.pop();
	 		res-=t;
		 }
		 ans=max(ans,res);
	 }
	 cout<<ans<<endl;
}
全部评论

相关推荐

06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务