题目
题目概要:
有一群牛在***你的花园,你现在知道每头牛离农场的要走的时间,与每头牛对花园的破坏速率。
求你用最好的方法把牛运回去之后,花园被***了多少花。
注意因为要一来一回,花的时间为2 * T。
输入描述:
第一行一个字母N,表示牛的数量。
接下来2~N+1行为牛的信息:运该牛要花的时间,与该牛的破坏速率。
输出描述:
一个整数表示被破坏的花的数量。
解析
知识点
- 这道题一看题目:哇,老贪心了。因为苣苣在上课的时候和我们讲过这种贪心的思路。
贪心策略
- 这个贪心策略很简单:假设我们现在有两头相邻搬运的牛。这两头牛交换顺序对答案可能有影响,但是对其他牛没有影响,所以贪心成立。
- 然后我们就假设两头牛分别在前面的情况,用来判断那种情况好(这里我们假设为A牛和B牛,sum表示在这两头牛之前花的时间):
- 如果先把A搬回去就有:sum * A.dedtroy + (sum + 2 * A.time) * B.destroy。
- 那如果先搬掉B呢就有:sum * B.destroy + (sum + 2 * B.time) * A.destroy。
- 那现在我们两种情况有了,我们接下来不妨设:A在前比B在前要更好!就可以得到方程:
- sum * A.dedtroy + (sum + 2 * A.time) * B.destroy < sum * B.destroy + (sum + 2 * B.time) * A.destroy。
- 化简之后就是:A.time * B.destroy < B.time * A.destroy。就是说只要满足这个,A就可以放在B的前面,反之亦然。
- 就这样~
算法操作
- 那怎么操作呢?知道算法之后操作不难:其实就是按照要求去排个序就好了。
- 排序我这里用到了结构体数组,然后重载运算符。
- 重载时的排序规律就按照上面推出来的。
打代码
- 首先输入数据,初始化结构体数组。
- 然后结构体数组排序。
- 最后累加输出。
- 看我完整代码趴~
AC代码
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 const int MAX = 1e5 + 7; struct Node { int time, destroy; bool operator < (const Node& v) const { return time * v.destroy < v.time * destroy; } } cow[MAX]; //全局变量区 int main() { IOS; int n; cin >> n; for (int i = 1; i <= n; i++) cin >> cow[i].time >> cow[i].destroy; sort(cow + 1, cow + 1 + n); ll time = 0, ans = 0; for (int i = 1; i <= n; i++) { ans += time * cow[i].destroy; time += 2 * cow[i].time; } cout << ans << endl; return 0; } //函数区