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

贴个c++代码

Posted by a280920481 at 2018-12-27 12:00:50 on Problem 3045
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;


const int MAX_S = 1000000005;
const int MAX_N = 50005;

struct Cow
{
	int s;
	int w;
	//重载运算符, 使之非升序排序
	bool operator < (const Cow & b)const
	{
		return s > b.s;
	}
}cow[MAX_N];

//最大堆
priority_queue<int, vector<int>, less<int> > que;

int N;

bool C(int risk, int tw);

int main()
{
	int tw = 0;//记录总重量
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> cow[i].w >> cow[i].s;
		cow[i].s += cow[i].w;//可以认为牛实际的s为真实的s加上自身的w
		tw += cow[i].w;
	}
	cow[N].s = -MAX_S;//设置哨兵
	cow[N].w = 0;

	sort(cow, cow + N + 1);

	int lb = -MAX_S, rb = MAX_S, mid;
	while (rb - lb > 1)
	{
		mid = (lb + rb) / 2;
		if (C(mid, tw))
		{
			rb = mid;
		}
		else
		{
			lb = mid;
		}
	}
	cout << rb << '\n';

	return 0;
}

bool C(int risk, int tw)
{
	int t = 0;

	for (int i = 0; t < N; i = t)
	{
		t = i;
		while (tw - cow[t].s <= risk)
		{
			que.push(cow[t].w);
			t++;
		}
		if (!que.empty())
		{
			tw -= que.top();//贪心选择w最大的牛, 因为能够进入que中的牛均可以承担后续牛的重量
			que.pop();
		}
		else
		{
			return false;
		}
	}

	while (!que.empty())
	{
		que.pop();
	}
	return true;
}

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