poj 3262 Protecting the Flowers 贪心

缘起

日常浪费生命 poj 3262 Protecting the Flowers

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
N头牛在吃花. 每头牛吃花的速度是di, FJ赶第i头牛回栏需要ti时间，然后ti时间回到花田. 假设此刻FJ可以不用
花费任何时间就赶到另一头牛的位置，然后继续赶这头牛. 求赶牛的最佳顺序使得吃掉的花数量最少.

【输入】
首先是N(2 ≤ N ≤ 100,000),然后N行，每行两个数字——(t,d), 1 ≤ Ti ≤ 2,000,000,1 ≤ Di ≤ 100

【输出】
最少损失的花朵数量

【样例输入】
6
3 1
2 5
2 3
3 2
4 1
1 6

【样例输出】
86

【限制】
2s

【来源】
USACO 2007 January Silver

假设顺序是 (t1,d1),….,(tn,dn)，则总共吃掉的花朵数量是

1
S = [d2*t1+d3*(t1+t2)+d4*(t1+t2+t3)+....+dn*(t1+...+t_{n-1})]*2

那么我们考虑一下赶牛的顺序. 其实这种问题思考的方式是如果交换相邻两个项的顺序的话（这一点在Johnson算法的时候用过），例如交换了di和d_{i-1}的位置的话，则重新计算一下时间，然后做差知道我们需要

1
d_{i+1}*ti-di*t_{i+1}<=0

即

1
ti/di 需要升序

所以我们可以断言——最佳顺序是使得ti/di递增的. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef long long LL;

LL n, st[100005]; // st 是部分和

struct Cow
{
	LL t,d;
	bool operator <(Cow c)
	{
		return 1.0*t/d<1.0*c.t/c.d;
	}
} cow[100005];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%lld", &n);
	for (int i = 1; i<=n; i++)
	{
		scanf("%lld%lld", &cow[i].t, &cow[i].d);
	}
	sort(cow+1, cow+n+1);
	for (int i = 1; i<=n; i++) st[i] = st[i-1]+cow[i].t;
	LL ans = 0;
	for (int i = 2; i<=n; i++) ans+=cow[i].d*st[i-1];
	printf("%lld\n",ans<<1);
	return 0;
}

ac情况

Status Accepted
Time 250ms
Memory 2452kB
Length 636
Lang C++
Submitted 2019-08-26 09:04:04
Shared
RemoteRunId 20801232