题目网址:http://codeforces.com/contest/1151/problem/D
题目大意:给出n组数对,(ai , bi),调整这n组数对的位置,最小化 ∑(ai*( i -1)+bi*(n - i))并输出结果。
题解:首先这个展开这个式子,并归变量得,i*(ai - bi)+n*bi,即这个式子之和前部分有关,后面的就是n*∑ bi,若要最小化总和,即按(ai - bi)配对,并逆序相乘即可。
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int maxn=1e5+7; 5 ll a[maxn],b[maxn],c[maxn]; 6 int main() 7 { 8 int n;ll ans=0; 9 cin>>n; 10 for(int i=1;i<=n;i++) { 11 scanf("%I64d %I64d",&a[i],&b[i]); 12 ans+=n*b[i]-a[i];c[i]=a[i]-b[i]; 13 } 14 sort(c+1,c+1+n); 15 int tot=0; 16 for(int i=n;i>=1;i--) 17 { 18 ans+=i*c[++tot]; 19 } 20 cout<<ans<<endl; 21 }View Code