题解 | #[USACO 2007 Jan S]Protecting the Flowers#
[USACO 2007 Jan S]Protecting the Flowers
https://ac.nowcoder.com/acm/problem/25043
寻找贪心策略的一道题，显然可知在中间两个相邻的牛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;
}
查看6道真题和解析
