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;
}