POJ_3262 Protecting the Flowers 【貪心】

一、題面

POJ3262

二、分析

這題要往貪心上面想應該還是很容易的，但問題是要證明為什么比值關系就能滿足。

可以選擇幾個去分析，入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\n", Ans);
36     return 0;
37 }

View Code

轉載于:https://www.cnblogs.com/dybala21/p/10150761.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/387724.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/387724.shtml
英文地址，請注明出處：http://en.pswp.cn/news/387724.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！