Codeforces Round #553 (Div. 2) D题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #553 (Div. 2) D题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1280字，纯文字阅读大概需要2分钟。

内容图文

题目网址：http://codeforces.com/contest/1151/problem/D

题目大意：给出n组数对,(ai , bi)，调整这n组数对的位置，最小化 ∑（ai*( i -1)+bi*(n - i)）并输出结果。<msub><mi>a</mi><mi>i</mi></msub><mo>&#x22C5;</mo><mo stretchy="false">(</mo><mi>j</mi><mo>&#x2212;</mo><mn>1</mn><mo stretchy="false">)</mo><mo>+</mo><msub><mi>b</mi><mi>i</mi></msub><mo>&#x22C5;</mo><mo stretchy="false">(</mo><mi>n</mi><mo>&#x2212;</mo><mi>j</mi><mo stretchy="false">)</mo></math>">

题解：首先这个展开这个式子，并归变量得，i*(ai - bi)+n*bi,即这个式子之和前部分有关，后面的就是n*∑ bi，若要最小化总和，即按（ai - bi）配对，并逆序相乘即可。

                 1 #include<bits/stdc++.h>
 2#define ll long long
 3usingnamespace std;
 4constint maxn=1e5+7;
 5ll a[maxn],b[maxn],c[maxn];
 6int main()
 7{
 8int n;ll ans=0;
 9     cin>>n;
10for(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);
15int tot=0;
16for(int i=n;i>=1;i--)
17    {
18         ans+=i*c[++tot];
19    }
20     cout<<ans<<endl;
21 }  

View Code

 

原文：https://www.cnblogs.com/duxing201806/p/10778368.html

内容总结

以上是互联网集市为您收集整理的Codeforces Round #553 (Div. 2) D题全部内容，希望文章能够帮你解决Codeforces Round #553 (Div. 2) D题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---