题解：AT_tkppc3_f 天使とふすま

· · 题解

hdu 多校 day1 1004 类似题。感觉好像这个题有一万个，至少我肯定曾经做过，结论记得很清楚，但没找到原。

赛时就靠着前世的记忆猜了个结论过了，但是可删堆实现成了答辩光荣爆炸，卡空间吃七罚忍无可忍，重构忘开 long long 再吃一罚，八罚愤怒变区。

题外话是，赛时给队友的 SA 板子，因为鸡排的实现过于优秀 memset 一个 10^5 的数组恰好 10^4 次，顺利给队友送上一罚。还好还好差点我们队就要无伤过题了 /hec

一眼贪心，考虑 exchange argument 来做。

考虑固定一个操作顺序，一个点的贡献其实就是前缀的 A 的和乘上当前的 B。

对于两个门 i,j，考虑他们的先后关系，若 i 前 j 后会产生 A_i\times B_j，反过来会产生 B_i\times A_j 的贡献。显然选择贡献小的方案。

把列出来的不等式给移项一下，我们得出结论，按照 \frac{A_i}{B_{i}} 升序排序即可。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fish{
    int a,b;
}a[200006];
bool cmp(fish x,fish y){
    return x.a*y.b<x.b*y.a;
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i].a>>a[i].b;
    sort(a+1,a+1+n,cmp);
    int ans=0,sum=0;
    for(int i=1;i<=n;i++)
    ans+=a[i].b*sum,sum+=a[i].a;
    cout<<ans;
    return 0;
}
//『我不会说就算感到伤心也不能哭这种话。只不过，别把这个当作不笑的理由。』
//『伤心时可以笑，开心时也可以哭。』