贪心

• 贪心：把整体问题分解成多个步骤，在每个步骤都选取当前步骤的最优方案，直至所有步骤结束；每个步骤不会影响后续步骤
• 核心性质：每次采用局部最优，最终结果就是全局最优
• 如果题目满足上述核心性质，则可以采用贪心进行求解

如何判断是否能用贪心？

1. 最优子结构性质：当一个问题的最优解包含子问题的最优解，则称之为具有最优子结构性质。
2. 贪心性质选择：可以通过局部最优的选择得到全局最优

具体问题如何做？

1. 经验性积累各种类型的贪心
2. 举反例

经典贪心

石子合并问题

石子合并问题：每次选择最小的两个

利用堆：heapq

题目描述

在很久很久以前，有 $n$ 个部落居住在平原上，依次编号为 $1$ 到 $n$。第 $i$ 个部落的人数为 $t_i$。

有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。

每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。

输入描述

输入的第一行包含一个整数 $n$，表示部落的数量。

第二行包含 $n$ 个正整数，依次表示每个部落的人数。

其中，$1\le n\le 1000，1\le t_i\le 10^4$。

输出描述

输出一个整数，表示最小花费。

import heapq
n = int(input())
a = list(map(int, input().split()))

# 把a转化为堆
heapq.heapify(a)
ans = 0
while len(a) >= 2:
    x = heapq.heappop(a)
    y = heapq.heappop(a)
    heapq.heappush(a, x + y)
    ans += x + y
print(ans)

分箱问题

每组最多两件，价值之和不超过 $w$

尽可能不浪费空间：大的和小的凑在一起

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入描述

第 $1$ 行包括一个整数 $w(80\le w\le 200)$，为每组纪念品价格之和的上限。

第 $2$ 行为一个整数 $n(1\le n\le 30000)$，表示购来的纪念品的总件数。

第 $3$~$n+2$ 行每行包含一个正整数 $p_i(5\le p_i\le w)$，表示所对应纪念品的价格。

输出描述

输出一行，包含一个整数，即最少的分组数目。

w = int(input())
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

a.sort()
l, r = 0, n - 1
ans = 0

while True:
    if l == r:
        ans += 1
        break
    if l > r:
        break
    if a[l] + a[r] <= w:
        ans += 1
        l += 1
        r -= 1
    else:
        ans += 1
        r -= 1
print(ans)

翻硬币问题

题目描述

小明正在玩一个"翻硬币"的游戏。

桌上放着排成一排的若干硬币。我们用 $\ast$ 表示正面，用 $o$ 表示反面（是小写字母，不是零）。

比如，可能情形是：$\ast \ast oo\ast \ast \ast oooo$;

如果同时翻转左边的两个硬币，则变为：$oooo\ast \ast \ast oooo$。

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入描述

两行等长的字符串，分别表示初始状态和要达到的目标状态。

每行的长度<1000。

输出描述

一个整数，表示最小操作步数。

s = list(input())
t = list(input())
n = len(s)
ans = 0
for i in range(n):
    if s[i] == t[i]:
        continue
    if s[i + 1] == '*':
        s[i + 1] = 'o'
    else:
        s[i + 1] = '*'
    ans += 1
print(ans)

数组乘积问题

给定两个长度为 $n$ 的正整数数组 $a$ 和 $b$，可以任意排序，求 ${\sum }_{i=1}^{n}a[i]\ast b[i]$ 的最小值

思路：$a$ 从小到大，$b$ 从大到小，然后对应元素相乘结果最小

参考个人博客：贪心