中级天翼
2619 赶牛
经验值：1200 时间限制：1000毫秒
题目描述 Description
农夫约翰家的N头牛在花园里大肆破坏，需要将他们赶紧赶回去。第i头牛到牛棚之间的距离要花费的时间为2*Ti，在第i头牛还没被赶回去之前，它会以每分钟Di的速度破坏花园。约翰一次只能弄回去一头牛。农夫约翰从牛棚到牛身边花费的时间忽略不计。请帮助约翰计算损失D最小能减少到多少。
输入描述 Input Description
第一行，一个整数，N
接下来N行，第i行两个整数，Ti Di
输出描述 Output Description
输出最小的总破坏D
样例输入 Sample Input
6 3 1 2 5 2 3 3 2 4 1 1 6
样例输出 Sample Output
86
数据范围及提示 Data Size & Hint
2 ≤ N ≤ 100,000
1 ≤ Ti ≤ 2,000,000
1 ≤ Di ≤ 100
WA12分代码：
#include<iostream>
#include<algorithm>
using namespace std;
int sum;
struct pohuai{
int shi,su;
}a[100005];
bool cmp(pohuai x,pohuai y){
if(x.su!=y.su){
return x.su>y.su;
}
return x.shi<y.shi;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].shi>>a[i].su;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
sum+=2*a[i].shi*a[j].su;
}
}
cout<<sum;
return 0;
}
中级启示者
错误点1：
对于两头牛，不能单单比较破坏力。
比如考虑先赶牛x还是牛y，应比较2×t[x]×d[y]和2×t[y]×d[x]（牛y在农夫赶牛x时造成的破坏，牛x在农夫赶牛y时造成的破坏）
化简得应比较t[x]×d[y]和t[y]×d[x]
cmp函数：
bool cmp(node a,node b){
return a.t*b.d<b.t*a.d;
}错误点2：
n<=10^5，O(n^2)会超时。
考虑前缀和，累加破坏力，实现O(1)求出总破坏
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i].d;
for(int i=1;i<=n;i++)
ans+=2*a[i].t*(sum[n]-sum[i]);错误点3：
没开long long
新手天翼
同上
缔造者之神
同上
