首页 > 代码库 > 【贪心】【堆】Gym -100956D - Greedy Game
【贪心】【堆】Gym -100956D - Greedy Game
题意：给定n个物品，每个物品对于A和B来说具有不同的价值，记为ai，bi，两人交替取，A先手，A总是贪心地取当前剩下的物品中，对于他价值最高的，如果有多个，则任取一个。问B在最坏情况下，能取到的物品的对他的价值和最大是多少。
先把物品以ai为第一关键字，bi为第二关键字排序。这样A每次必定从最左端取。容易发现，A必定会在2,3中取至少1个，在2,3,4,5中取至少2个，在2,3,4,5,6,7中取至少3个……因此，一开始，我们假设B取得的都是偶数位的物品，然后更新这些当前最优的物品集合，发现，如果把这个集合中的物品换成它右侧的物品，仍然可以保证合法，因此，可以从左到右枚举物品，维护一个小根堆，尝试用奇数位的物品去更新当前堆，保证堆里面的物品是当前最优的，最后堆里面剩下的就是答案。具体看代码。
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> Point;
priority_queue<int,vector<int>,greater<int> >heap;
Point a[100010];
bool cmp(const Point &a,const Point &b)
{
return a.first!=b.first ? a.first>b.first : a.second>b.second;
}
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i].first);
for(int i=1;i<=n;++i)
scanf("%d",&a[i].second);
sort(a+1,a+n+1,cmp);
for(int i=2;i<n;i+=2)
{
heap.push(a[i].second);
int x=heap.top();
if(x<a[i+1].second)
{
heap.pop();
heap.push(a[i+1].second);
}
}
ll ans=0;
if(n%2==0)
ans=a[n].second;
while(!heap.empty())
{
ans+=heap.top();
heap.pop();
}
cout<<ans<<endl;
return 0;
}
【贪心】【堆】Gym -100956D - Greedy Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。