放牧代码和思想
专注自然语言处理、机器学习算法

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//////////////////////////////////
12816535 hankcs 3045 Accepted 644K 422MS C++ 1123B 2014-04-28 23:58:39

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

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

分享到:更多 ()

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    楼主还在读书吗

    qingxi曾4年前 (2015-03-22)回复
  2. #1

    的确用贪心就能解决的题目…二分的效率貌似反而低了

    小泣喵喵咪4年前 (2014-07-10)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机