Codeforces Round #553 (Div. 2) D题

题目网址: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)配对,并逆序相乘即可。

Codeforces Round #553 (Div. 2) D题
 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

 

上一篇:【DB笔试面试553】在Oracle中,什么是不可见索引?


下一篇:EdgexGo2.0学习-20 编译EdgeX Go UI