POJ 3262 Protecting the Flowers 题解 《挑战程序设计竞赛(第2版)》

2.2 一往直前！贪心法 其他

POJ 3262 Protecting the Flowers

保护祖国的花朵：约翰的奶牛每分钟吃掉D_i朵花，把它赶走需要T_i分钟（来回加倍）。问最小损失花朵数量。

贪心策略是尽量赶走吃得多并且走得慢的牛，如何衡量“多”“慢”？需要两头牛作比较:

bool operator < (const Cow& c) const
	{
		return T * c.D < c.T * D;
	}

然后一个排序，按顺序赶牛就行了。注意int溢出WA。

#include <iostream>
#include <algorithm>
using namespace std;

struct Cow
{
	int T;
	int D;
	bool operator < (const Cow& c) const
	{
		return T * c.D < c.T * D;
	}
};

Cow cow[100000];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	int total_destory = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> cow[i].T >> cow[i].D;
		total_destory += cow[i].D; // 总的损害
	}
	sort(cow, cow + N);
	unsigned long long destroied = 0;
	for (int i = 0; i < N; ++i)
	{
		total_destory -= cow[i].D;
		destroied += total_destory * cow[i].T * 2; // 损害维持时间为2倍的 moving 牛耗时
	}
	cout << destroied << endl;
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3262 Protecting the Flowers 题解 《挑战程序设计竞赛(第2版)》