贪心学习总结

0928_14

·

2023-07-17 20:36:49

·

个人记录

1.贪心概念

贪心是最接近现实生活的一种编程思想。它是一种"策略"或"序",原理是通过每次选择局部最优来求出全局最优,通过每一次的"决策"来逐步缩小问题的规模,归纳成更小的子问题,最后求出问题解。

2.贪心的正确性

不论是什么算法,都有正确和错误,贪心也是如此。想要证明贪心的正确,是非常复杂的。相比而言,证明贪心的错误就简单多了,一般有反证法和调整法。

反证法

反证法顾名思义,通过举出反例来证明当前贪心策略的错误；

调整法

调整法相对复杂,通过当前贪心策略制造出问题解S1,若与最优解S2不同,则在不改变最优的情况下逐步调整S2,从而得出S1也是最优解。

例题:删数问题

键盘输入一个高精度的正整数 NN（不超过 250250 位），去掉其中任意 kk 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 NN 和 kk，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数 n。

第二行输入一个正整数 kk，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

输入输出样例

输入

175438

4

输出

13

直觉告诉我们:去掉最大的数字!

那对不对呢?样例貌似是符合这个贪心策略的。

怎么可能对呢

思考过后我们会发现:不能这么做!

比如以下反例:17289 3

正确答案是:128!!!

但如果按照上面的策略,答案应该是172

这样,我们通过反证法就成功证明了贪心策略的错误。

3.贪心题目

A.最值类问题

例题:

【题目描述】

你有 C 只蜈蚣， 每只蜈蚣有 F 只脚。 冬天来了， 要给蜈蚣们穿袜子。 抽屉里有 N 种颜色的袜子， 第 i 种颜色袜子的数量有 a[i]只。 对于一只蜈蚣来说， 它所有的脚穿的袜子的颜色必须相同。 现在你闭上眼睛， 从抽屉里面随意拿出 X 只袜子， 你要保证随意拿出来的 X 只袜子

一定可以满足所有蜈蚣的需求。 那么 X 的最小值是多少？ 如果 X 不存在， 输出-1。

【输入格式】

第一行， 三个整数， C， F， N。 1<=C<=50， 1<=F<=100， 1<=N<=100。

第二行， N 个整数， 第 i 个整数是 a[i]。 1 <= a[i] <= 10000000。

【输出格式】

一个整数。 最小的 X， 如果 X 不存在， 输出-1。

【输入样例】

1 100 5

1 1 1 1 100

【输出样例】

104

首先确定贪心策略:"保证"+"最少"=多浪费问题(就是必要地多浪费袜子)

其次,这道题可以分成四部分:

(1)必取部分

1.C*F只穿的袜子必须拿。

2.因为要有必要地浪费,所以比F只少的要拿走。说好的环保呢

(2)-1部分

只要满足不了C只,就输出-1

满足只数=a[1]/F+a[2]/F+......+a[n-1]/F+a[n]/F

(3)预留(F-1)只后仍能满足蜈蚣

每一项预留(F-1)之后,如果还能满足所有蜈蚣,那么除最后一只都能浪费(F-1)只(每一项都能预留(F-1)只,那肯定能浪费(F-1)只)

所以,*浪费数=(n-1)(F-1)**

(4)预留(F-1)只后不能满足所有蜈蚣

首先统计数组后,需要更新数组

*a[i]=a[i]-(a[i]-(F-1))/FF**(凑袜子后剩下只数)

其次,有(C-num)只蜈蚣(num指凑袜子能满足多少蜈蚣),没有满足,所以还能浪费（j-(C-num))*(F-1)只

B.区间问题

例题:

Description

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1..n。每个块的大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b，e，t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b<=e，居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t<=e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因，环保部门请你求出能够满足所有居民的要求，需要种树的最少数量。

Input

第一行为n，表示区域的个数；

第二行为h，表示房子的数目；

下面h行描述居民的需要：b e t (1<=b<=e<=30000,r<=e-b+1) 分别用一个空格分开。

Output

输出为满足所有要求的最少树的数量。

Sample Input

9

4

1 4 2

4 6 2

8 9 2

3 5 2

Sample Output

5

首先确定贪心思想:在重叠部分种尽可能多的数让总棵树最少。

这是属于贪心的区间问题,一般以右指针排序,但有时也会以左指针排序。

因为重叠部分在末尾,所以这道题以右指针排序。

首先对起点到终点进行查询,确定还需种的树；之后从尾到头进行种树并进行计数,最后输出即可。我还想了半天

The End

总结到此结束