题目网址: 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) 配对, 并逆序相乘即可.
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int maxn=1e5+7;
- ll a[maxn],b[maxn],c[maxn];
- int main()
- {
- int n;ll ans=0;
- cin>>n;
- for(int i=1;i<=n;i++) {
- scanf("%I64d %I64d",&a[i],&b[i]);
- ans+=n*b[i]-a[i];c[i]=a[i]-b[i];
- }
- sort(c+1,c+1+n);
- int tot=0;
- for(int i=n;i>=1;i--)
- {
- ans+=i*c[++tot];
- }
- cout<<ans<<endl;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3037739.html