Problem Description

Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport each cow back to its own barn.

Each cow i is at a location that is Ti minutes (1 ≤ Ti ≤ 2,000,000) away from its own barn. Furthermore, while waiting for transport, she destroys Di (1 ≤ Di ≤ 100) flowers per minute. No matter how hard he tries, FJ can only transport one cow at a time back to her barn. Moving cow i to its barn requires 2 × Ti minutes (Ti to get there and Ti to return). FJ starts at the flower patch, transports the cow to its barn, and then walks back to the flowers, taking no extra time to get to the next cow that needs transport.
Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.

Input

Line 1: A single integer N?
Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics

Output

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

Sample Input

6

3 1
2 5
2 3
3 2
4 1
1 6

Sample Output

86

題意：將n頭牛趕回牛圈，每頭牛在被趕之前每秒破壞Di朵花，趕牛回去要花Ti×2的時間，在趕牛的過程中，牛不能破壞花，求趕完所有牛后，被破壞花的最小值。

思路：

典型貪心算法，先對牛的破壞度進行排序，然后順序趕牛計算破壞度即可。

設兩頭牛 A、B，要先趕走破壞大的，留下破壞小的牛。若先趕走 A，則 B 造成 2×TA×DB 的損失；若先趕走B，則 A 造成 2×TA×DB 的損失，因此判斷?TA×DB 與 TA×DB 即可。

推廣到 n 頭牛，則排序標準為：Ti×Dj > Tj×Di

Source Program

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 100100 #define MOD 123 #define E 1e-6 using namespace std; struct Node {long long x;long long y; }a[N];int cmp(Node a,Node b) {return b.x*a.y>a.x*b.y; }int main() {int n;while(scanf("%d",&n)!=EOF){memset(a,0,sizeof(a));long long sum=0;for(int i=0;i<n;i++){scanf("%lld%lld",&a[i].x,&a[i].y);sum+=a[i].y;//計算所有牛在花園中每秒的破壞度}sort(a,a+n,cmp);//對牛按破壞度排序long long num=0;for(int i=0;i<n-1;i++){sum-=a[i].y;//趕走一頭牛后，減去該牛在花園中每秒的破壞度num+=2*sum*(a[i].x);//計算當前總破壞度}printf("%lld\n",num);}return 0; }

?

總結

以上是生活随笔為你收集整理的Protecting the Flowers（POJ-3262）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。