【每日一题】Protecting the Flowers
Protecting the Flowers
https://ac.nowcoder.com/acm/problem/25043
题目
题目概要：
有一群牛在***你的花园，你现在知道每头牛离农场的要走的时间，与每头牛对花园的破坏速率。
求你用最好的方法把牛运回去之后，花园被***了多少花。
注意因为要一来一回，花的时间为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;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
查看24道真题和解析