POJ_3262 Protecting the Flowers 【贪心】

一、题面

二、分析

这题要往贪心上面想应该还是很容易的，但问题是要证明为什么比值关系就能满足。

可以选择几个去分析，入1-6 与 2-15 和 1-6 与2-5 和 1-6 与 2- 12。

三、AC代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <fstream>
 5 using namespace std;
 6 
 7 const int MAXN = 1e5+6;
 8 
 9 struct Cow
10 {
11     int time, flower;
12 }Data[MAXN];
13 
14 bool Cmp(const Cow a, const Cow b)
15 {
16     return (double)a.flower/a.time > (double)b.flower/b.time;
17 }
18 
19 int main()
20 {
21     //freopen("input.txt", "r", stdin);
22     int N;
23     scanf("%d", &N);
24     for(int i = 0; i < N; i++)
25     {
26         scanf("%d %d", &Data[i].time, &Data[i].flower);
27     }
28     sort(Data, Data+N, Cmp);
29     long long T = 0, Ans = 0;
30     for(int i = 0; i < N; i++)
31     {
32         Ans += Data[i].flower*T;
33         T += 2*Data[i].time;
34     }
35     printf("%I64d
", Ans);
36     return 0;
37 }

View Code