题集

题意

  • 基本都隐含着让最大贡献尽可能小

思路

  • 贪心来思考，在局部让他对总贡献小，那么在全局就贡献小，这类问题，往往一个单位的贡献情况只取决于自身和前面一位，也就是说，交换自身和前一位对除了这俩以外的部分没有影响，那么便可以进行讨论
  • 以保护那些花为例：我们不妨假设两只牛按的排列方式是最优的，也就是毁坏的花比小。
  • 那么，毁坏的花为：,毁坏的花为：
  • 两式相消可得出：

AC代码

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