备战蓝桥杯-----贪心算法基础知识(专题一)

8-毛俊杰
8-毛俊杰   编辑于 2018-12-25 16:16
阅读量: 218

贪心算法

贪心算法顾名思义就是用计算机来模拟一个 “贪心” 的人做出决策的过程。

这个人每一步行动总是按某种指标选取最优的操作,他总是 只看眼前,并不考虑以后可能造成的影响 

可想而知,并不是所有的时候贪心法都能获得最优解,所以一般使用贪心法的时候,都要确保自己能证明其正确性。

基础习题八道

左边的题目是oj的题目地址,后面的连接是题解。

「一本通 1.1 例 1」活动安排https://www.cnblogs.com/mbath/p/10170028.html

「一本通 1.1 例 2」种树https://www.cnblogs.com/mbath/p/10170102.html

「一本通 1.1 例 3」喷水装置https://www.cnblogs.com/mbath/p/10171988.html

「一本通 1.1 例 4」加工生产调度https://www.cnblogs.com/mbath/p/10172101.html

「一本通 1.1 例 5」智力大冲浪https://www.cnblogs.com/mbath/p/10172120.html

「一本通 1.1 练习 1」数列极差https://www.cnblogs.com/mbath/p/10172151.html

「一本通 1.1 练习 2」数列分段https://www.cnblogs.com/mbath/p/10172270.html

「一本通 1.1 练习 3」线段https://www.cnblogs.com/mbath/p/10172301.html

常见做法

 

在基础算法题中,最常见的贪心有两种。一种是:「我们将 XXX 按照某某顺序排序,然后按某种顺序(例如从小到大)处理」。另一种是:「我们每次都取 XXX 中最大 / 小的东西,并更新 XXX」,有时「XXX 中最大 / 小的东西」可以优化,比如用优先队列维护。

你可以发现,一种是离线的,一种是在线的。

证明方法

从来都是大胆猜想,从来不会小心求证。

以下套路请按照题目自行斟酌,一般情况下一道题只会用到其中的一种方法来证明。

  1. 运用反证法,如果交换方案中任意两个元素 / 相邻的两个元素后,答案不会变得更好,那么可以发现目前的解已经是最优解了。
  2. 运用归纳法,先手算得出边界情况(例如\((n=1)\)  )的最优解  \(F1\),然后再证明:对于每个 \(n,F_{n+1}\) 都可以由\(F_n\)  推导出结果。

排序法

用排序法常见的情况是输入一个包含几个(一般一到两个)权值的数组,通过排序然后遍历模拟计算的方法求出最优值。

有些题的排序方法非常显然,如 luogu P1209 就是将输入数组差分后排序模拟求值。

然而有些时候很难直接一下子看出排序方法,比如 luogu P1080 就很容易凭直觉而错误地以  或 为关键字排序,过样例之后提交就发现 WA 了 QAQ。一个 众所周知的 常见办法就是尝试交换数组相邻的两个元素来推导出正确的排序方法。我们假设这题输入的俩个数用一个结构体来保存。

后悔法

例题 luogu P2949 [USACO09OPEN] 工作调度 Work Scheduling

贪心思想:

  • 1 . 先假设每一项工作都做,将各项工作按截止时间排序后入队。
  • 2 . 在判断第 i 项工作做与不做时,若其截至时间符合条件,则将其与队中报酬最小的元素比较,若第 i 项工作报酬较高(后悔),则 ans+=a[i].p-q.top()。

PS : 用优先队列(小根堆)来维护队首元素最小。

题解代码:

#include <bits/stdc++.h>
using namespace std;
struct node{
    int tim,mny;
}w[100001];
int n,i;
long long ans;
priority_queue<int,vector<int>,greater<int> > q;
bool cmp(node a,node b){
    return a.tim<b.tim;
}
int main(){
    scanf("%d",&n);
    for (i=1; i<=n; i++)
        scanf("%d%d",&w[i].tim,&w[i].mny);
    sort(w+1,w+n+1,cmp);
    for (i=1; i<=n; i++){
        if (w[i].tim<=q.size()){
            if (w[i].mny>q.top()){
                ans-=q.top();
                q.pop(); q.push(w[i].mny);
                ans+=w[i].mny;
            }
        }
        else{
            q.push(w[i].mny);
            ans+=w[i].mny;
        }
    }
    printf("%lld",ans);
    return 0;
}

 

收藏 转发 评论 1

差不多该带着搞别的了