USACO2007 Protecting the Flowers比值 前缀和 oj21161

题目大意：

 有N (2 ≤ N ≤ 100,000) 头牛偷吃花

将牛赶回牛棚需T_i minutes (1 ≤ T_i ≤ 2,000,000)

每头牛每分钟能吃D_i (1 ≤ D_i ≤ 100) 朵花

则赶牛的来回需2*T_i minutes (T_i to get there and T_i to return)

Input

* Line 1: A single integer N

* Lines 2..N+1: Each line contains two space-separated integers, T_i and D_i, that describe a single cow's characteristics

Output

* Line 1: A single integer that is the minimum number of destroyed flowers

Sample Input

63 12 52 33 24 11 6

Sample Output

86

 

一开始用DFS 结果TLE

#include <bits/stdc++.h> using namespace std; long long n,ans,sum; struct cow { double t,f,s; }a[100005]; bool cmp(struct cow a,struct cow b) { return a.s>b.s; } int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lf%lf",&a[i].t,&a[i].f); a[i].s=a[i].f/a[i].t; ///s为每分钟吃花的数量与赶牛时间的比值 选取耗时少且吃花多的牛能最大限度地减少损失 则应先赶s更大的牛 sum+=a[i].f; ///利用前缀和 省略每次重新循环计量的浪费 } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { sum-=a[i].f; ans+=a[i].t*sum*2; } printf("%lld\n",ans); return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8359509.html