贪心

本页面将简要介绍贪心算法。

引入

贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

意思就是说，贪心算法并不能产生问题的最优解，只能产生目前的全局最优解。

解释

适用范围

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解

要点

常见题型

在提高组难度以下的题目中，最常见的贪心有两种。

• 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。」。
• 「我们每次都取 XXX 中最大/小的东西，并更新 XXX。」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）

二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。

排序解法

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

后悔解法

思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

区别

与动态规划的区别

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

例题

[NOIP2012 提高组] 国王游戏

题目描述

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 $n$，表示大臣的人数。

第二行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

样例 #1

样例输入 #1

1
2
3
4
5

3 
1 1 
2 3 
7 4 
4 6

样例输出 #1

1

2

提示

【输入输出样例说明】

按 $1$、$2$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $1$、$3$、$2$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按 $2$、$1$、$3$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 2$、$3$、$1 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$；

按 $3$、$1$、$2 $这样排列队伍，获得奖赏最多的大臣所获得金币数为 $2$；

按$ 3$、$2$、$1$ 这样排列队伍，获得奖赏最多的大臣所获得金币数为 $9$。

因此，奖赏最多的大臣最少获得 $2$ 个金币，答案输出 $2$。

【数据范围】

对于 $20\%$ 的数据，有 $1≤ n≤ 10,0 < a,b < 8$；

对于 $40\%$ 的数据，有$ 1≤ n≤20,0 < a,b < 8$；

对于 $60\%$ 的数据，有 $1≤ n≤100$；

对于 $60\%$ 的数据，保证答案不超过 $10^9$；

对于 $100\%$ 的数据，有 $1 ≤ n ≤1,000,0 < a,b < 10000$。

NOIP 2012 提高组 第一天 第二题

题解

贪心部分:

对于第 i个大臣和第 j 个大臣:

如果第 i 个大臣放第 j 个大臣前面对答案的贡献小些,那么第 i 个大臣就放第 j 个大臣前面

所以就是使a[i].x/a[j].y<a[j].x/a[i].y

所以就是a[i].x∗a[i].y<a[j].x∗a[j].y

然后高精度部分压位,这样快得多,20ms,

乘法部分相当于高精度乘低精度

除法部分相当于高精度除低精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include<bits/stdc++.h>
using namespace std;
int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(s>='0'&&s<='9')
    {
        k=k*10+(s-'0');
        s=getchar();
    }
    return k*base;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        write(-x);
    }
    else
    {
        if(x/10)write(x/10);
        putchar(x%10+'0');
    }
}
int n,A,B;
struct node
{
    int x,y;
} a[1010];
bool cmp(node aa,node bb)
{
    if (aa.x*aa.y==bb.x*bb.y) return aa.y<bb.y;
    return (aa.x*aa.y)<(bb.x*bb.y);
}
int sum[1010];
int ans[1010],ls;
int p[1010],lp;
int m;//sum长度
int P;
bool Max()//比大小,ans>p: true
{
    int i=1;
    while (p[i]==0&&i<=lp) i++;//去掉前面的0
    int j=1;
    while (ans[j]==0&&j<=ls) j++;
    if (lp-i+1>ls-j+1) return false;//p的位数>ans的位数
    if (lp-i+1<ls-j+1) return true;
    while (i<=lp&&j<=ls)//一位一位的比较
    {
        if (p[i]<ans[j]) return true;
        if (p[i]>ans[j]) return false;
        i++;
        j++;
    }
    return false;
}
void cheng(int d)
{
    for (int i=1;i<=m;i++)
        sum[i]*=a[d].x;//高精度乘法
    for (int i=1;i<=m;i++)//进位
    {
        sum[i+1]+=sum[i]/10000;
        sum[i]%=10000;
    }
    if (sum[m+1]!=0) m++;
}
void div(int d)
{
    memset(ans,0,sizeof(ans));
    ls=1;
    while (m>0&&sum[m]==0) m--;//去掉前导0
    P=0;
    int flag=0;
    for (int i=m;i>=1;i--)//高精度除法(模拟竖式)
    {
        P=P*10000+sum[i];
        ans[++ls]=P/a[d].y;
        if (ans[ls]==0&&!flag) ls--; else flag=1;
        P%=a[d].y;
    }
}
int main()
{
    n=read();
    A=read();
    B=read();
    for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    sort(a+1,a+n+1,cmp);
    m=1;
    sum[1]=A;
    for (int i=1;i<=n;i++)
    {
        div(i);
        if (Max())
        {
            lp=ls;
            memcpy(p,ans,sizeof(ans));
        }
        cheng(i);
    }
    int i=0;
    while (i<=lp&&p[i]==0) i++;
    printf("%d",p[i]);i++;
    for (;i<=lp;i++)//输出
    {
        if (0<=p[i]&&p[i]<=9) printf("000%d",p[i]);else
        if (10<=p[i]&&p[i]<=99) printf("00%d",p[i]);else
        if (100<=p[i]&&p[i]<=999) printf("0%d",p[i]);else
        printf("%d",p[i]);
    }
    return 0;
}

练习

[USACO1.3] 修理牛棚 Barn Repair

题目描述

在一个月黑风高的暴风雨夜，Farmer John 的牛棚的屋顶、门被吹飞了 好在许多牛正在度假，所以牛棚没有住满。

牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。

自门遗失以后，Farmer John 必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。 Farmer John 想将他购买的木板总长度减到最少。

给出 $m,s,c$，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛棚所需木板的最小总长度。

输入格式

一行三个整数 $m,s,c$，意义如题目描述。
接下来 $c$ 行，每行包含一个整数，表示牛所占的牛棚的编号。

输出格式

输出一行一个整数，表示所需木板的最小总长度。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4 50 18
3 
4 
6 
8 
14
15 
16 
17 
21
25 
26 
27 
30 
31 
40 
41 
42 
43

样例输出 #1

1

25

提示

【数据范围】
对于 $100%$ 的数据，$1\le m \le 50$，$1\le c \le s \le 200$。

USACO Training Section 1.3

关于

本文内容些许借鉴OI Wiki

本文作者Minecraft-Sep