jzoj 1276. 护花

jzoj 1276. 护花

Description

　　FJ出去砍木材去了，把N(2<=N<=100,000)头牛留在家中吃草，当他回来的时候，发现奶牛们都跑到花园里吃花去了，为了减少损失，FJ打算把牛移到牛棚中去。
　　每头牛的位置离牛棚需要Ti分钟(1<=Ti<=2,000,000)，而且在等待被移走的过程中，每分钟破坏Di(1<=Di<=100)朵花，无论多么努力FJ一次只能移动一只奶牛，移动一只奶牛到牛棚需要2×Ti分钟(来回各一次)。
　　写一个程序安排移动顺序使得损失的花最少。

Input

　　第1行输入一个整数N
　　第2到N+1行每行包含两个整数Ti和Di

Output

　　输出一个整数表示最少损失的花的数量

Sample Input

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

Sample Output

86

Data Constraint

Hint

【样例说明】
FJ按照6、2、3、4、1、5的顺序移走奶牛

分析：
对于两头牛i和j，则先把i带走的代价是Ti*Dj,而把j先带走代价是Tj ∗ <script type="math/tex" id="MathJax-Element-36">*</script>Di,判断这两个数的大小，用此来进行快排就好了。

代码：

vara,b:array [1..100000] of longint;n,i:longint;ans,time:int64;procedure qsort(l,r:longint);var mid,i,j,key_a,key_b,t:longint;
beginif l>r then exit;i:=l; j:=r;mid:=(l+r) shr 1;key_a:=a[mid];key_b:=b[mid];repeatwhile a[i]*key_b<b[i]*key_a do inc(i);while a[j]*key_b>b[j]*key_a do dec(j);if i<=j thenbegint:=a[i]; a[i]:=a[j]; a[j]:=t;t:=b[i]; b[i]:=b[j]; b[j]:=t;inc(i); dec(j);end;until i>j;qsort(l,j);qsort(i,r);
end;beginreadln(n);for i:=1 to n dobeginread(a[i],b[i]);end;qsort(1,n);time:=0; ans:=0;for i:=1 to n dobeginans:=ans+time*b[i];time:=time+a[i]*2;end;writeln(ans);
end.