题解 P2878 【[USACO07JAN]保护花朵Protecting the Flowers】

我顺着这道题讲一下贪心策略吧 # 一、贪心是什么？ 贪心就是一种“目光短浅”的算法，之所以目光短浅是因为它只考虑眼下的事情，而不考虑长远，这也使得贪心的时空复杂度普遍偏低 贪心的优势：速度快，空间少 贪心的劣势：策略难想且大部分试题只能做骗分工具使用 当然学好贪心对拿分还是很有好处的 # 二、简单的贪心 部分背包问题：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 故可以按照此标准排序，下面给出程序： ------------ ```cpp #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从大到小的顺序依次交代即可 ## 喵就是这样