题目

题目概要:
有一群牛在***你的花园,你现在知道每头牛离农场的要走的时间,与每头牛对花园的破坏速率。
求你用最好的方法把牛运回去之后,花园被***了多少花。
注意因为要一来一回,花的时间为2 * T。

输入描述:
第一行一个字母N,表示牛的数量。
接下来2~N+1行为牛的信息:运该牛要花的时间,与该牛的破坏速率。

输出描述:
一个整数表示被破坏的花的数量。


解析

知识点

  • 这道题一看题目:哇,老贪心了。因为苣苣在上课的时候和我们讲过这种贪心的思路。

贪心策略

  1. 这个贪心策略很简单:假设我们现在有两头相邻搬运的牛。这两头牛交换顺序对答案可能有影响,但是对其他牛没有影响,所以贪心成立
  2. 然后我们就假设两头牛分别在前面的情况,用来判断那种情况好(这里我们假设为A牛和B牛,sum表示在这两头牛之前花的时间):
  3. 如果先把A搬回去就有:sum * A.dedtroy + (sum + 2 * A.time) * B.destroy。
  4. 那如果先搬掉B呢就有:sum * B.destroy + (sum + 2 * B.time) * A.destroy。
  5. 那现在我们两种情况有了,我们接下来不妨设:A在前比B在前要更好!就可以得到方程:
  6. sum * A.dedtroy + (sum + 2 * A.time) * B.destroy < sum * B.destroy + (sum + 2 * B.time) * A.destroy
  7. 化简之后就是:A.time * B.destroy < B.time * A.destroy。就是说只要满足这个,A就可以放在B的前面,反之亦然。
  8. 就这样~

算法操作

  1. 那怎么操作呢?知道算法之后操作不难:其实就是按照要求去排个序就好了。
  2. 排序我这里用到了结构体数组,然后重载运算符
  3. 重载时的排序规律就按照上面推出来的。

打代码

  1. 首先输入数据,初始化结构体数组。
  2. 然后结构体数组排序。
  3. 最后累加输出。
  4. 看我完整代码趴~


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;
}
//函数区