【每日一题】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;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏