缘起
日常浪费生命 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
|
即
所以我们可以断言——最佳顺序是使得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("
for (int i = 1; i<=n; i++)
{
scanf("
}
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("
return 0;
}
|
ac情况
| Status |
Accepted |
| Time |
250ms |
| Memory |
2452kB |
| Length |
636 |
| Lang |
C++ |
| Submitted |
2019-08-26 09:04:04 |
| Shared |
|
| RemoteRunId |
20801232 |