Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

DP+优先队列

Posted by ACAccepted at 2019-04-29 16:59:03 on Problem 2010
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=100005;
int n,m,k;

struct cows
{
	int score,cost;
	
	bool operator < (const cows tmp) const
	{
		return score>tmp.score;
	}
}cow[MAXN];
int l[MAXN],r[MAXN];

priority_queue<int,vector<int>,less<int> > Q;

int main()
{
	n=read();m=read();k=read();
	for (int i=1;i<=m;i++)
		cow[i].score=read(),cow[i].cost=read();
	sort(cow+1,cow+m+1);
	int sum=0,half_n=(n-1)/2;
	for (int i=1;i<=half_n;i++)sum+=cow[i].cost,Q.push(cow[i].cost);
	l[half_n]=sum;
	for (int i=half_n+1;i<=m;i++)
	{
		if (cow[i].cost<Q.top())
		{
			sum=sum-Q.top()+cow[i].cost;
			Q.pop();Q.push(cow[i].cost);
		}
		l[i]=sum;
	}
	sum=0;
	while (!Q.empty())Q.pop();
	for (int i=m;i>=m-half_n+1;i--)sum+=cow[i].cost,Q.push(cow[i].cost);
	r[half_n]=sum;
	for (int i=m-half_n;i>=1;i--)
	{
		if (cow[i].cost<Q.top())
		{
			sum=sum-Q.top()+cow[i].cost;
			Q.pop();Q.push(cow[i].cost);
		}
		r[i]=sum;
	}
	int ans=-1;
	for (int i=half_n+1;i<=m-half_n;i++)
		if (l[i-1]+cow[i].cost+r[i+1]<=k){ans=cow[i].score;break;}
	printf("%d\n",ans);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator