自动搬运

查看原文

来自洛谷，原作者为

	曦行夜落 精 罗 落 泪

搬运于2025-08-24 21:42:56，当前版本为作者最后更新于2018-06-05 19:37:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

一、贪心是什么？

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

二、简单的贪心

部分背包问题：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从大到小的顺序依次交代即可

喵就是这样