贪心算法初步

Author： RainAir
发布时间：July 16, 2018
946views
No comments
2472 words
Categories：学习笔记

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。（摘自百度百科）

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

建立数学模型来描述问题；</p>
<p>把求解的问题分成若干个子问题；</p>
<p>对每一子问题求解，得到子问题的局部最优解；</p>
<p>把子问题的解局部最优解合成原来解问题的一个解。 <h1>题目</h1> 贪心算法没有固定的结构，需要我们从多个题目去探讨。 <h2>1.合并果子</h2>

题目链接

给您一个数列，合并数列中两个数的代价是这两个数的和，求合并为一个数的最小代价。

解题报告

这种题目，我们发现无论如何，先合并较小的两个数子是最优的。

考虑如果我们先合并代价较大的那两个，就会使得之后的所有合并都带上这个额外值。

所以我们需要能插入数字，删除数字和快速查询最大值的数据结构。（优先队列）

我们如果把合并过程画出来，会发现它是一棵 Huffman 树。

代码：

pre>

include <iostream>

include <cstdio>

include <queue>

include <functional>

std::priority_queue <int,std::ector<int>,std::greater<int> > heap;
int main(){

int n,x,ans = 0;
scanf("%d",&amp;n);
for(int i = 1;i &lt;= n;i++){
    scanf("%d",&amp;x);
    heap.push(x);
}
for(int i = 1;i &lt; n;i++){
    int a = heap.top();
    heap.pop();
    int b = heap.top();
    heap.pop();
    ans += a+b;
    heap.push(a+b);
}
cout&lt;&lt;ans&lt;&lt;endl;
return 0;

}
</pre>

建议先完成1.合并果子

题目描述

构建一棵$ K $进制的Huffman编码。

Huffman树的构建过程就是贪心。

我们每次讲当前最小的父节点合并，直到合并完成。

如果不是满$ K $叉树，自己补上空结点即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define LL long long

struct Tree{
    LL v,h;
    
    bool operator < (const Tree &a) const {
        if(v != a.v) return v > a.v;
        return h > a.h;
    }
};

std::priority_queue<Tree> q;
int N,K;

int main(){
    scanf("%d %d",&N,&K);
    for(int i = 1;i <= N;++i){
        Tree a;
        scanf("%lld",&a.v);
        a.h = 1;
        q.push(a);
    }
    LL top = 0;
    if((N-1) % (K-1) != 0) top += K-1-(N-1)%(K-1);
    for(int i = 1;i <= top;i++){
        Tree need;
        need.v = 0;need.h = 1;
        q.push(need);
    }
    top += N;
    LL ans = 0;
    while(top != 1){
        Tree a;
        LL t = 0,max = 0;
        for(int i = 1;i <= K;i++){
            a = q.top();
            t += a.v;
            max = std::max(max,a.h);
            q.pop();
        }
        ans += t;
        a.v = t;
        a.h = max + 1;
        q.push(a);
        top -= K-1;
    }
    printf("%lldn%lldn",ans,q.top().h-1);
    return 0;
}

数轴上有$ n $条线段，问要覆盖区间$ [l,r] $至少需要多少条线段。

首先，我们按照左端点对所有线段排序。

然后，我们在剩下的所有线段中找出所有左端点小于等于当前已经覆盖的区间中的右端点，且该线段与要求线段有交，右端点最大的一个。

证明：我们希望用线段的数量最少，就要让每条线段对总体的贡献最大。而已经覆盖的部分再次覆盖是没有贡献的。所以我们就找没有被覆盖的部分最大的一个。

代码：没有评测地址，没写。

题目链接

恰逢H国国庆，国王邀请n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。</p>
<p>国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。</p>
<p>n<=1000 <h3>解题报告</h3> 我们尽量让左右手乘积最大的在后面。证明：我们设队伍中国王身后两个大臣$a$，$b$的左右手分别是$ l_a $，$ r_a $和$ l_b $， $r_b$。我们考虑交换这两个人，对后面的人的结果都没有影响。那我们单独分析这两个人：设$a $在$ b $前面时答案为$ ans_1 $，$ a $在$ b $后面是答案为$ ans_2 $。 $$ ans_1 = max{\frac{l_a}{r_a},\frac{l_a*l_b}{r_b}} $$ $$ ans_2 = max{\frac{l_b}{r_b},\frac{l_a*l_b}{r_a}}$$</p>

<p>替换，得

$$ ans_1 = max{k_1,k_2} $$

$$ ans_2 = max{k_3,k_4} $$

比较，得：

$$ \frac{l_a*l_b}{r_b} > \frac{l_b}{r_b} \to k_2 > k_3 $$

$$ \frac{l_a*l_b}{r_a} > \frac{l_a}{r_a} \to k_4 > k_1 $$

我们设$ ans_1 < ans_2 $

那么得$ k_4 > k_2 $

即：$ \frac{l_a * l_b}{r_a} > \frac{l_a*l_b}{r_b} $

变形得：$ l_a * r_a < l_b * r_b $

所以得：当$ l_a * r_a < l_b * r_b $时，$ ans_1 < ans_2 $

该题要求最大值最小，我们就让乘积小者在前，大者在后，排序计算即可。

还有，要写高精度

代码：有高精度，不给。

<h2>5.阿狸和桃子的游戏</h2>

有一个有点权有边权的图，然后两个人分别给每个点染色。</p>
<p>对于一个点的点权将会赐予染了这个点的人。对于一条边的边权，若它连接的两个点被同一个人染了，那么边权会赐予这个人。</p>
<p>它们两个人都想让自己的分数减去对方的分数尽可能多。</p>
<p>输出最终双方的分数差。 <h3>解题报告</h3> 我们将每一个边的边权一分为二，放到相连的两个点上。然后排个序，从最大的开始选即可。证明：如果两个点被不同的人选了，那么都会增加相同的得分，导致差没有改变。如果被同一个人选了，那就增加了这条边的全部。代码：</p>

  #include <algorithm>
  #include <iostream>
  #include <cstring>
  #include <climits>
  #include <cstdlib>
  #include <cstdio>
  #include <cmath>
  #include <queue>
  #include <stack>
  #include <map>
  #include <set>
  
  int N,M;
  double ans = 0;
  const int MAXN = 10000 + 5;
  
  double dist[MAXN];
  
  bool cmp(double a,double b){
    return a > b;
  }
  
  int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= N;i++)
        scanf("%lf",&dist[i]);
    for(int i = 1;i <= M;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        double delta = (double)(w/2.);
        dist[u] += delta;dist[v] += delta;
    }
    std::sort(dist + 1,dist + N + 1,cmp);
    for(int i = 1;i <= N;i++){
        if(i & 1) ans += dist[i];
        else ans -= dist[i];
    }
    printf("%.lf",ans);
    getchar();getchar();
    return 0;
  }

<p>题目链接

神犇航空开展了一项载客特技飞行业务。每次飞行长$ N $个单位时间，每个单位时间可以进行一项特技动作，可选的动作有$ K $种，每种动作有一个刺激程度$ C_i $。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间)*$ C_i $，若为第一次进行该动作，价值为$ 0 $。安排一种方案，使得总价值最大。

首先明确：对于同一个动作，做超过一次的任意次数，所得的结果一定。

那么我们要尽量让刺激程度高的动作间隔时间长，所以我们就要用环状来构图。

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

const int MAXN = 1000 + 5;

int N,K;
int c[MAXN];

bool cmp(int a,int b){
    return a > b;
}

int main(){
    scanf("%d%d",&N,&K);
    for(int i = 1;i <= K;i++)
        scanf("%d",&c[i]);
    std::sort(c + 1,c + K + 1,cmp);
    int l = 1,r = N,ans = 0;
    for(int i = 1;i <= N;i++){
        ans += (r - l) * c[i];
        l++;r--;
        if(l >= r) break;
    }
    printf("%dn",ans);
    return 0;
}

Last modification：April 7th, 2020 at 10:14 pm

如果觉得我的文章对你有用，请随意赞赏

贪心算法初步

RainAir • 2018 年 07 月 16 日

建立数学模型来描述问题；</p>
<p>把求解的问题分成若干个子问题；</p>
<p>对每一子问题求解，得到子问题的局部最优解；</p>
<p>把子问题的解局部最优解合成原来解问题的一个解。 <h1>题目</h1> 贪心算法没有固定的结构，需要我们从多个题目去探讨。 <h2>1.合并果子</h2>

题目链接

给您一个数列，合并数列中两个数的代价是这两个数的和，求合并为一个数的最小代价。

解题报告

这种题目，我们发现无论如何，先合并较小的两个数子是最优的。

考虑如果我们先合并代价较大的那两个，就会使得之后的所有合并都带上这个额外值。

所以我们需要能插入数字，删除数字和快速查询最大值的数据结构。（优先队列）

我们如果把合并过程画出来，会发现它是一棵 Huffman 树。

代码：

pre>

include <iostream>

include <cstdio>

include <queue>

include <functional>

std::priority_queue <int,std::ector<int>,std::greater<int> > heap;
int main(){

int n,x,ans = 0;
scanf("%d",&amp;n);
for(int i = 1;i &lt;= n;i++){
    scanf("%d",&amp;x);
    heap.push(x);
}
for(int i = 1;i &lt; n;i++){
    int a = heap.top();
    heap.pop();
    int b = heap.top();
    heap.pop();
    ans += a+b;
    heap.push(a+b);
}
cout&lt;&lt;ans&lt;&lt;endl;
return 0;

}
</pre>

建议先完成1.合并果子

题目描述

构建一棵$ K $进制的Huffman编码。

Huffman树的构建过程就是贪心。

我们每次讲当前最小的父节点合并，直到合并完成。

如果不是满$ K $叉树，自己补上空结点即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define LL long long

struct Tree{
    LL v,h;
    
    bool operator < (const Tree &a) const {
        if(v != a.v) return v > a.v;
        return h > a.h;
    }
};

std::priority_queue<Tree> q;
int N,K;

int main(){
    scanf("%d %d",&N,&K);
    for(int i = 1;i <= N;++i){
        Tree a;
        scanf("%lld",&a.v);
        a.h = 1;
        q.push(a);
    }
    LL top = 0;
    if((N-1) % (K-1) != 0) top += K-1-(N-1)%(K-1);
    for(int i = 1;i <= top;i++){
        Tree need;
        need.v = 0;need.h = 1;
        q.push(need);
    }
    top += N;
    LL ans = 0;
    while(top != 1){
        Tree a;
        LL t = 0,max = 0;
        for(int i = 1;i <= K;i++){
            a = q.top();
            t += a.v;
            max = std::max(max,a.h);
            q.pop();
        }
        ans += t;
        a.v = t;
        a.h = max + 1;
        q.push(a);
        top -= K-1;
    }
    printf("%lldn%lldn",ans,q.top().h-1);
    return 0;
}

数轴上有$ n $条线段，问要覆盖区间$ [l,r] $至少需要多少条线段。

首先，我们按照左端点对所有线段排序。

然后，我们在剩下的所有线段中找出所有左端点小于等于当前已经覆盖的区间中的右端点，且该线段与要求线段有交，右端点最大的一个。

代码：没有评测地址，没写。

题目链接

恰逢H国国庆，国王邀请n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。</p>
<p>国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。</p>
<p>n<=1000 <h3>解题报告</h3> 我们尽量让左右手乘积最大的在后面。证明：我们设队伍中国王身后两个大臣$a$，$b$的左右手分别是$ l_a $，$ r_a $和$ l_b $， $r_b$。我们考虑交换这两个人，对后面的人的结果都没有影响。那我们单独分析这两个人：设$a $在$ b $前面时答案为$ ans_1 $，$ a $在$ b $后面是答案为$ ans_2 $。 $$ ans_1 = max{\frac{l_a}{r_a},\frac{l_a*l_b}{r_b}} $$ $$ ans_2 = max{\frac{l_b}{r_b},\frac{l_a*l_b}{r_a}}$$</p>

<p>替换，得

$$ ans_1 = max{k_1,k_2} $$

$$ ans_2 = max{k_3,k_4} $$

比较，得：

$$ \frac{l_a*l_b}{r_b} > \frac{l_b}{r_b} \to k_2 > k_3 $$

$$ \frac{l_a*l_b}{r_a} > \frac{l_a}{r_a} \to k_4 > k_1 $$

我们设$ ans_1 < ans_2 $

那么得$ k_4 > k_2 $

即：$ \frac{l_a * l_b}{r_a} > \frac{l_a*l_b}{r_b} $

变形得：$ l_a * r_a < l_b * r_b $

所以得：当$ l_a * r_a < l_b * r_b $时，$ ans_1 < ans_2 $

该题要求最大值最小，我们就让乘积小者在前，大者在后，排序计算即可。

还有，要写高精度

代码：有高精度，不给。

<h2>5.阿狸和桃子的游戏</h2>

有一个有点权有边权的图，然后两个人分别给每个点染色。</p>
<p>对于一个点的点权将会赐予染了这个点的人。对于一条边的边权，若它连接的两个点被同一个人染了，那么边权会赐予这个人。</p>
<p>它们两个人都想让自己的分数减去对方的分数尽可能多。</p>
<p>输出最终双方的分数差。 <h3>解题报告</h3> 我们将每一个边的边权一分为二，放到相连的两个点上。然后排个序，从最大的开始选即可。证明：如果两个点被不同的人选了，那么都会增加相同的得分，导致差没有改变。如果被同一个人选了，那就增加了这条边的全部。代码：</p>

  #include <algorithm>
  #include <iostream>
  #include <cstring>
  #include <climits>
  #include <cstdlib>
  #include <cstdio>
  #include <cmath>
  #include <queue>
  #include <stack>
  #include <map>
  #include <set>
  
  int N,M;
  double ans = 0;
  const int MAXN = 10000 + 5;
  
  double dist[MAXN];
  
  bool cmp(double a,double b){
    return a > b;
  }
  
  int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= N;i++)
        scanf("%lf",&dist[i]);
    for(int i = 1;i <= M;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        double delta = (double)(w/2.);
        dist[u] += delta;dist[v] += delta;
    }
    std::sort(dist + 1,dist + N + 1,cmp);
    for(int i = 1;i <= N;i++){
        if(i & 1) ans += dist[i];
        else ans -= dist[i];
    }
    printf("%.lf",ans);
    getchar();getchar();
    return 0;
  }

<p>题目链接

首先明确：对于同一个动作，做超过一次的任意次数，所得的结果一定。

那么我们要尽量让刺激程度高的动作间隔时间长，所以我们就要用环状来构图。

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

const int MAXN = 1000 + 5;

int N,K;
int c[MAXN];

bool cmp(int a,int b){
    return a > b;
}

int main(){
    scanf("%d%d",&N,&K);
    for(int i = 1;i <= K;i++)
        scanf("%d",&c[i]);
    std::sort(c + 1,c + K + 1,cmp);
    int l = 1,r = N,ans = 0;
    for(int i = 1;i <= N;i++){
        ans += (r - l) * c[i];
        l++;r--;
        if(l >= r) break;
    }
    printf("%dn",ans);
    return 0;
}

贪心算法初步

解题报告

include <iostream>

include <cstdio>

include <queue>

include <functional>

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「JZOJ6281」串

CF1394 题解

Timus2157 Skydiving

SRM579 RockPaperScissors

「CF103E」Buying Sets

贪心算法初步

解题报告

include <iostream>

include <cstdio>

include <queue>

include <functional>