题目
Protecting the Flowers
Time Limit: 2000MS Memory Limit: 65536KDescription
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 OutputLine 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 6Sample Output
86
Hint
FJ returns the cows in the following order: 6, 2, 3, 4, 1, 5. While he is transporting cow 6 to the barn, the others destroy 24 flowers; next he will take cow 2, losing 28 more of his beautiful flora. For the cows 3, 4, 1 he loses 16, 12, and 6 flowers respectively. When he picks cow 5 there are no more cows damaging the flowers, so the loss for that cow is zero. The total flowers lost this way is 24 + 28 + 16 + 12 + 6 = 86.
题目大意
题目描述
FJ去砍树，然后和平时一样留了 N (2 ≤ N ≤ 100,000)头牛吃草。当他回来的时候，他发现奶牛们正在津津有味地吃着FJ种的美丽的花！为了减少后续伤害，FJ决定立即采取行动：运输每头牛回到自己的牛棚。 每只奶牛i在离牛棚Ti(1 ≤ Ti ≤ 2,000,000) 分钟路程的地方，每分钟吃掉Di(1 ≤ Di ≤ 100)朵花。FJ使尽浑身解数，也只能一次带回一头奶牛。弄回一头奶牛i需要2*Ti分钟（来回）。由于怕被怼，从FJ决定带回i号奶牛开始，i号奶牛就不会吃花。请你找出被毁坏的花的最小数量 .
样例提示
FJ的顺序是： 6, 2, 3, 4, 1, 5.当找回6、2、3、4、1、5时，损失花数量分别为24、28、16、12、6、0 。 24 + 28 + 16 + 12 + 6 = 86.
思路
又是一类a*b的问题，首先想到的就是比较Di*Ti然后排序，但这样显然不行，从样例和提示即可看出，那么要怎么比较呢，小小推理一下：
设当前要比较的两头牛为i和j，他们的数据为Di,Ti和Dj,Tj。
设此时FJ已经花费了x分钟运送之前的牛，则： ① 先运送第i头牛，i已经吃掉了x*Ti朵花 再运送第j头牛，j已经吃掉了(x+Di*2)*Tj朵花 一共吃了x*Ti+(x+Di*2)*Tj朵花 ② 先运送第j头牛，j已经吃掉了x*Tj朵花 再运送第i头牛，i已经吃掉了(x+Dj*2)*Ti朵花 一共吃了x*Tj+(x+Dj*2)*Ti朵花 所以，需要比较x*Ti+(x+Di*2)*Tj和x*Tj+(x+Dj*2)*Ti，但是x不知道啊，我们需要化简一下：
不妨设x*Ti + (x+Di*2)*Tj > x*Tj + (x+Dj*2)*Ti
x*Ti + (x+Di*2)*Tj - x*Tj - (x+Dj*2)*Ti > 0 =>x*Ti + x*Tj + 2*Di*Tj - x*Tj - x*Ti - 2*Dj*Ti >0 =>2*Di*Tj - 2*Dj*Ti > 0 =>Di*Tj - Dj*Ti > 0 =>Di*Tj > Dj*Ti 这样x就被抵消掉了，只需以Di*Tj和Dj*Ti排序即可。
代码
#include#include #include using namespace std;#define MAXN 100000#define LL long longstruct node{ int d,t;}cows[MAXN+5];int N;bool cmp(node x,node y){ return y.d*x.t