【贪心】【堆】Gym -100956D

题意：给定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

最新文章

热门文章