寻找贪心策略的一道题,显然可知在中间两个相邻的牛A和牛B的位置进行互换并不会影响左右两部分的数值。所以将AB和BA的结果进行比较可以得到贪心策略为:
D/T大的需要在前面。
代码:
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
struct Node {
    //把羊弄走的时间
    double t;
    //每分钟能吃多少草
    double d;
};
Node a[100005];

bool comp(Node n1, Node n2) {
    return n1.d/n1.t>=n2.d/n2.t;
}

int main() {
    ll N;
    scanf("%lld",&N);
    for (int i=0;i<N;i++) {
        scanf("%lf %lf", &a[i].t, &a[i].d);
    }
    sort(a, a+N, comp);
    //计算最终结果
    double ans = 0, time = 0;
    for (int i=0;i<N;i++) {
        ans += time*a[i].d;
        time += a[i].t*2;
    }
    printf("%.0lf", ans);
    return 0;
}