【每日一题】Protecting the Flowers

题意描述

有n头奶牛跑到FJ的花园里去吃花儿了，它们分别在距离牛圈T分钟处吃花儿，每分钟会吃掉D朵卡哇伊的花儿，（此处有点拗口，不要在意细节啊！），FJ现在要将它们给弄回牛圈，但是他每次只能弄一头回去，来回用时总共为2*T分钟，在这段时间内，其它的奶牛会继续吃FJ卡哇伊的花儿，速度保持不变，当然正在被赶回牛圈的奶牛就没口福了！现在要求以一种最棒的方法来尽可能的减少花儿的损失数量，求奶牛吃掉花儿的最少朵数！

输入描述:
Line 1: A single integer N
Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics

输出描述:
Line 1: A single integer that is the minimum number of destroyed flowers

思路

显然可以看出此题具有很明显的贪心的特征，我们把其中两只奶牛的运输放在一起看，那么对剩下奶牛的影响与这两头奶牛运输的先后顺序无关，所以取决两头奶牛运输顺序的就是这两头奶牛在不同顺序下的损耗。我们把这两头牛的时间分别设为x1,x2,把他们的每分钟的食草速度设成y1,y2.
如果先运奶牛1： 造成的损耗是：x1 * y2
如果先运奶牛2： 造成的损耗是：x2 * y1
那么我们得到的排序方式的代码段就是：

bool cmp(int x,int y){
    return a[x]*b[y]<b[x]*a[y];
}

有了顺序就能算出最小损失

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) x&(-x)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int N = 1e5+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps =1e-9;
const double PI=acos(-1.0);
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const int exdir[4][2]={1,1,1,-1,-1,1,-1,-1};

ll qpow(ll x,ll y){
    ll ans=1,t=x;
    while(y>0){
        if(y&1)ans*=t,ans%=mod;
        t*=t,t%=mod;
        y>>=1;
    }
    return ans%mod;
}
ll a[N],b[N],c[N],sum[N];
bool cmp(int x,int y){
    return a[x]*b[y]<b[x]*a[y];
}
void solve(){
    int n;cin>>n;
    for(int i=0;i<n;i++)cin>>a[i]>>b[i];
    for(int i=0;i<n;i++)c[i]=i;
    sort(c,c+n,cmp);
    for(int i=0;i<n;i++){
        int now=c[i];
        sum[i]+=b[now];
        if(i)sum[i]+=sum[i-1];
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        int now=c[i];
        ans+=(sum[n-1]-sum[i])*a[now]*2;
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int t;cin>>t;
    //while(t--)solve(),cout<<'\n';
    solve();
    return 0;
}