贪心、双指针、二分
11 贪心
11.1 定义
11.2 适用情况
如何判断？？？！
11.3 实例
11.3.1 石子合并
只考虑一步，每次都找最小的
那么问题的核心就是：如何选出最小的！
#石子合并
import heapq
n = int(input())
a =list(map(int,input().split()))
#堆每次弹出最小值
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)11.3.2 分组问题（纪念品分组）
w=int(input())
n=int(input())
a=[]#创建一个空列表
for i in range(n):
a.append(int(input())) #遍历n次，每次输入一个数，添加到a列表上去
a.sort() #把输入的数组排序
ans=0
l,r = 0,n-1 #下标
while True:
if l==r: #此时只有一个中间值，单独为一组
ans += 1
break
if l>r: #直接停止循环
break
if a[l]+a[r] <=w:
l += 1
r -= 1
ans += 1
else:
r -= 1
ans += 1
print(ans)11.3.3 翻硬币问题
翻的时候一下翻两个！
a=list(str(input()))
b=list(str(input()))
ans=0
for i in range(len(a)):
if a[i]!=b[i]:
if a[i]=="*":
a[i]="o"
else:
a[i]="*"
if a[i+1]=="*":
a[i+1]="o"
else:
a[i+1]="*"
ans+=1
print(ans)12 双指针
12.1 定义
双指针！！！
一般用于列表或者字符串里
12.2 例子
12.2.1 回文字符串
从前面读和从后面读是一样的
#回文字符串
#方法一
s = input()
i = 0
l = len(s)-1
while i<=l:
if s[i]==s[l]:
i = i+1
l = l-1
continue
# print("Yes")
else:
print("NO")
break
#方法2
s = input()
s1 = s[::-1]
if s ==s1:
print("YES")
else:
print('NO')12.2.2 通向扫描（滑动窗口）
#滑动窗口找美丽区间
def input_list():
return list(map(int,input().split()))
n,s = input_list()
#n是列表的长度
# print(type(n))
a = input_list()
l = 0
r = -1
len_list = []
tot = 0
#判断while超界不的主要依据要综合list！！！！一起看就不会纠缠在一起了！！！！！！！！！
while l<=n-1:
while r<n-1 and tot <s:
r += 1
tot += a[r]
if tot >= s:
len_ =r-l+1
print('左边是：',l)
print('右边是：',r)
print(len_)
# print(len)
len_list.append(len_)
tot -=a[l]
l = l+1
print(len_list)
if len(len_list) ==0:
print("没有美丽区间")
else:
print("最美丽区间长度为：",(min(len_list)))
12.2.3 挑选字串
#挑选字串
def input_list():
return list(map(int,input().split()))
n,m,k=input_list()
#n个数
#k个数字大于m
a = input_list()
#a是数组
l = 0
r = -1
cnt = 0
ans = 0
while l <= n-1:
while r < n-1 and cnt < k:
r += 1
if a[r] >= m:
cnt += 1
if cnt >= k:
ans += n-r
if a[l] >= m:
cnt -= 1
l += 1
print(ans)
13 二分
13.1 定义
二分法的前提：单调性？？！
例子：
题目中一般涉及的是 整数的二分法！
二分代码的模板
13.2 例子
【pay attention！！！：最大最小化谁 就把谁二分!】
13.2.1 分巧克力
找到单调性：（才可以用二分法！！）
x越大k越小
#分巧克力
def input_list():
return list(map(int,input().split()))
#当边长为x的时候，是否可以切除k个巧克力
def check(x,a,k):
cnt = 0#表示能切除的块数
for H,W in a:
cnt += (H//x)*(W//x)
return cnt >=k
N,K = input_list()
#N块巧克力 K位小朋友
a =[]
for i in range(N):
H_W = input_list() #N块巧克力的尺寸
a.append(H_W)
#找到边长
l = 1#边长是1 的时候肯定成立
r = 100000
ans = 1
while l <=r:
mid = (l+r)//2
if check(mid,a,K):
ans = mid
l = mid+1
else:
r = mid-1
print(ans)
13.2.2 跳石头
找到单调性：移走的石头越多那么最短跳跃距离越大！
求解：最短跳跃距离最大的这种问题可以提炼称【最小值最大化、最大值最小化等】这种问题一般就要使用二分法！
# 跳石头
def input_list():
return list(map(int,input().split()))
#当最短距离是x的时候，撤M个延时是否能够满足
def check(x,a,M):
cnt = 0#表示移走的岩石数
last_idx = 0
for i in range(1,len(a)-1):
if a[i] - a[last_idx]>=x:
last_idx = i
else:
cnt += 1#不满足这个石头挪走
if a[len(a)-1] - a[last_idx] >=x and cnt <=M:
return True
L,N,M = input_list()
#一共N块岩石，最多挪走M个
#L表示岩石距离起点距离的上界
a = [0]
for i in range(N):
a.append(int(input()))
l = 1
r = 1000000000
ans = 1
while l <=r:
mid = (l+r)//2
if check(mid,a,M):
ans = mid
l = mid+1
else:
r = mid-1
print(ans)
13.2.3 肖恩的乘法表
意思就是：第二行就是 第一行对应乘以2就可以
找到排序之后的第k个元素》》》则二分的对象是k
单调性是：k大则比k小的数多；k小比k小的数少
#肖恩乘法表
def input_list():
return list(map(int,input().split()))
n,m,k = input_list()
#n行m列，求排在第k位的元素
#求出小于x的有几个
def check(x,n,m,k):
cnt = 0
for i in range(1,n+1):
# i,2i,3i,4i,...,mi
#m * i <x >>>> m <x//i
cnt += min(m,x//i)
if cnt >= k:
return True
ans = 0
l = 0
r = n*m
while l <=r:
mid = (l+r) //2
if check(mid,n,m,k):
ans = mid
r = mid-1
else:
l = mid +1
print(ans)
