我顺着这道题讲一下贪心策略吧

一、贪心是什么？

贪心就是一种“目光短浅”的算法，之所以目光短浅是因为它只考虑眼下的事情，而不考虑长远，这也使得贪心的时空复杂度普遍偏低
贪心的优势：速度快，空间少
贪心的劣势：策略难想且大部分试题只能做骗分工具使用
当然学好贪心对拿分还是很有好处的

二、简单的贪心

部分背包问题：P1208
这种问题就是说：给定n种可任意分割的物品，每种物品有重量w和价值v，按照你选取重量的比例给你价值，但是全部物品的重量不得超过M
分析：既然可以分割，那就按照性价比v/w排序，然后依次选取直到空间不够为止

不重叠线段选取问题：P1803
给定n个区间，选取尽量多的不重叠区间
分析：首先要让区间尽量多，每个区间的右端点就得尽量小（腾出位置），所以按照右端点排序，然后依次选取不相交的区间（从前往后）

这种题目有很多，主要是顺着题目的想法走，直接或间接地最小化要求的量

三、更难一些的贪心（我才不会告诉你我不会更难的了）

比如本题：
这类贪心一般通过分析前后两个整体的交换来实现
本题中，我们讨论牛x与牛y
先抓x：2×t[x]×d[y]
先抓y：2×t[y]×d[x]
此时的优劣取决于t[x]×d[y]与t[y]×d[x]的大小，前者小先抓x，后者小先抓y
故可以按照此标准排序，下面给出程序：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define maxn 100000+500
using namespace std;
long long sum[maxn];

struct cows
{
    long long d,t;
}a[maxn];

int cmp(cows x,cows y)
{
    return x.t*y.d<x.d*y.t;
}

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%lld%lld",&a[i].t,&a[i].d);
    sort(a+1,a+1+n,cmp);
//	for (int i=1;i<=n;++i) printf("%d %d\n",a[i].t,a[i].d);
    
    for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i].d;
    long long ans=0;
    for (int i=1;i<=n;++i)
        ans+=2*a[i].t*(sum[n]-sum[i]);
    printf("%lld",ans);
    
    return 0;
}

例如，UVA11729的突击战，有n个任务，每个任务有交代时间a和执行时间b，每时每刻只能交代一个任务，问最少要多少时间完成全部任务
考虑任务x和y：
若x在y之前——
如果y比x先结束，那么交换后y反而延后，此时反而亏
如果y比x后结束，那么此时交换前总时间是a[x]+a[y]+b[y]，交换后为a[y]+a[x]+b[x]，根据x在y前得出a[x]+a[y]+b[y]<a[y]+a[x]+b[x]
化简得到b[x]>b[y]，推广到每一个x和y即可得出：
按照b从大到小的顺序依次交代即可

喵就是这样

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
struct node{LL t, d;} a[N];
bool cmp(node n1, node n2){
    return n1.t*n2.d < n2.t*n1.d;
}
int main(){
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld%lld", &a[i].t, &a[i].d);
        a[i].t *= 2;
    }
    sort(a+1, a+n+1, cmp);
    LL sum=0, ans=0;
    for(int i=1; i<=n; i++){
        ans += sum * a[i].d;
        sum += a[i].t;
    }
    printf("%lld\n", ans);
    return 0;
}