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