每日一题 5.28 Protecting the Flowers

这是一道贪心的比较经典的题
我们要知道对于牵牛回去的顺序来说 其中相邻的 a b 两者交换对于他们前面和后面是没有影响的
于是就有了
牵a回去的代价是: a.t * b.d * 2
牵b回去的代价是： b.t * a.d * 2
两者一比较化简 cmp函数里就写 a.tb.d<b.ta.d 注意答案范围超过了int

 #include <bits/stdc++.h>
#define ll long long
const int N=1e5+5;
using namespace std;
ll n,sumd,ans;
struct T
{
    ll t,d;
}a[N];
bool cmp(T a,T b)
{
    return a.t*b.d<b.t*a.d;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i].t>>a[i].d;sumd+=a[i].d;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i)
    {
        sumd-=a[i].d;
        ans+=sumd*a[i].t*2;
    }
    cout<<ans<<endl;
    return 0;
}