POJ 3045 Cow Acrobats 题解 《挑战程序设计竞赛》

POJ 3045 Cow Acrobats

犇：将N头牛叠成犇，每头牛的力气是S_i，体重是W_i，倒下的风险是身上的牛的体重和减去S_i，求最稳定犇的最大risk

平时不学习，昨天期中考试复习到凌晨五点，一整天腾云驾雾一般，晚上A一题醒醒神

事实上，牛的叠放顺序可以确定，并且相当方便。凭感觉，力量越大、体重越大的牛应该放在越下面，否则浪费力气。所以按下面的代码排过序后就是叠放顺序，然后顺序找出最大risk即可。

其实我根本没看出跟二分有什么关系，硬要说的话，似乎可以在搜索最大risk的时候设定一个mid，然后顺序计算risk是否小于mid，不过也太多此一举了吧。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_N 50000 + 16

struct Cow
{
	int weight, strength;
	bool operator < (const Cow& other) const
	{
		return other.strength + other.weight < strength + weight;
	}
};

Cow cow[MAX_N];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int N;
	cin >> N;
	int total = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> cow[i].weight >> cow[i].strength;
		total += cow[i].weight;
	}
	sort(cow, cow + N);
	int risk = 0x80808080;
	for (int i = 0; i < N; ++i)
	{
		total -= cow[i].weight;						// 减去自己的重量
		risk = max(risk, total - cow[i].strength);	// 计算risk
	}
	cout << risk << endl;
	
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

如果你知道这题怎么利用二分提高效率，欢迎留言。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3045 Cow Acrobats 题解 《挑战程序设计竞赛》