首页 > 代码库 > poj3262 Protecting the Flowers
poj3262 Protecting the Flowers
思路:
简单贪心,每次选择性价比最高的。
实现:
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 struct node 7 { 8 int t, d; 9 }; 10 int n; 11 node a[100005]; 12 int sum[100005]; 13 14 bool cmp(const node & a, const node & b) 15 { 16 double x = a.d * 1.0 / a.t; 17 double y = b.d * 1.0 / b.t; 18 return x > y; 19 } 20 21 int main() 22 { 23 cin >> n; 24 for (int i = 0; i < n; i++) 25 { 26 scanf("%d %d", &a[i].t, &a[i].d); 27 } 28 sort(a, a + n, cmp); 29 sum[n - 1] = a[n - 1].d; 30 for (int i = n - 2; i >= 0; i--) 31 { 32 sum[i] = sum[i + 1] + a[i].d; 33 } 34 long long total = 0; 35 for (int i = 0; i < n - 1; i++) 36 { 37 total += sum[i + 1] * 2 * a[i].t; 38 } 39 cout << total << endl; 40 return 0; 41 }
poj3262 Protecting the Flowers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。