题目链接

https://ac.nowcoder.com/acm/problem/25043

题目描述

题目：
Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport each cow back to its own barn. Each cow i is at a location that is Ti minutes (1 ≤ Ti ≤ 2,000,000) away from its own barn. Furthermore, while waiting for transport, she destroys Di (1 ≤ Di ≤ 100) flowers per minute. No matter how hard he tries, FJ can only transport one cow at a time back to her barn. Moving cow i to its barn requires 2 × Ti minutes (Ti to get there and Ti to return). FJ starts at the flower patch, transports the cow to its barn, and then walks back to the flowers, taking no extra time to get to the next cow that needs transport. Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.

输入描述

Line 1: A single integer N
Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics

输出描述

Line 1: A single integer that is the minimum number of destroyed flowers

简要翻译

背景：咱就靠卖花过日子了，自家牛居然在吃花田里的花，太可恶了！必须把它们赶回牛圈里狠狠修正！现在告诉你有n只牛，第i只牛被赶回牛圈的时间为（单程时间），它吃花的速度为每单位时间，需要将所有的牛都赶回牛圈里。现在要求将所有的牛都赶回去后最终损失的花最少值为多少。

思路

本题其实就是要给所有的牛牛排个序，依次送回牛圈。我们记所有的n头牛最终排序后依次为(i=1...n)，在这个序列中，我们找到相邻的两头牛牛A和B，假设A排在B前面，那么序列可以看作
如果B排在A前面，则序列变成
此时不难发现，对于AB之前和AB之后排序中的牛，这些牛吃掉花的量不会因为AB的顺序发生改变，那么只需要比较这两种情况下AB总共吃掉花的量就能比较出谁放在前面更合适。

提出假设

不妨设A在B前时，吃掉的花总量更少。在这种情况下可以计算出
A吃的草量为
B吃的草量为
如果B在A前面，则
A吃的草量为
B吃的草量为

根据假设可以推出
把式子都带进去再化简一下就能得到当且仅当时，满足我们的前提假设，那么在一开始直接就按照这个比例对所有的牛牛排序一下就行。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 100010;
int n;
struct node{
    int t, d;
    bool operator < (const node& other) const{
        return (double)t/d < (double)other.t/other.d;
    }
}cows[N];

signed main(){
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> cows[i].t >> cows[i].d;
    }
    sort(cows, cows + n);
    int ans = 0;
    int time = cows[0].t * 2;
    for (int i = 1; i < n; i++){
        ans += time * cows[i].d;
        time += cows[i].t * 2;
    }
    cout << ans;
    return 0;
}

总结与发散

本题总结

哇，是不是一下就觉得这个题好简单啊。这种贪心算法的题算是一种模板题了，遇到需要得出一个排序序列的都可以按照这个相邻两个元素之间的先后关系求出两种情况的花销，然后再根据前提假设进行不等式推导，最终用这个不等式对原数组排序。

举一反三

1. NC16561国王的游戏 https://ac.nowcoder.com/acm/problem/16561