https://ac.nowcoder.com/acm/contest/329/D

題解：std

貪心思想。按照ai/bi 作為關鍵字進行排序，按順序完成作業即可。

時間復雜度：?(? log N)

#include <bits/stdc++.h> using namespace std;int n; pair<int,int> a[100005]; bool cmp(const pair<int,int> &a, const pair<int,int> &b) {return 1.0*a.first/a.second<1.0*b.first/b.second; } int main() {int n;scanf("%d",&n);int sum=0;long long ans=0;for (int i=1;i<=n;i++){scanf("%d%d",&a[i].first,&a[i].second);sum+=a[i].second;}sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i++){sum-=a[i].second;ans+=(long long)a[i].first*sum;}printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的处女座的训练的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。