寻找贪心策略的一道题,显然可知在中间两个相邻的牛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; }