【Python蓝桥杯备赛宝典】

一、基础数据结构

1.1 链表

1.2 队列

1.3 栈

1.4 二叉树

1.5 堆

二、基本算法

2.1 算法复杂度

2.2 尺取法

2.3 二分法

2.4 三分法

2.5 倍增法和ST算法

2.6 前缀和与差分

2.7 离散化

2.8 排序与排列

2.9 分治法

2.10贪心法

1.接水时间最短问题

题目描述
有n个人在一个水龙头前排队接水，假如每个人接水的时问为T，请编程找出这n个人排队的一种顺序
使得n个人的平均等待时间最小。
输入格式
第一行为一个整数n。
第二行n个整数，第i个整数T表示第i个人的接水时间T
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序：第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

说明/提示
1≤n≤1000.1≤t≤10，不保证t不重复
代码展现

n=int(input())
b=list(map(int,input().split()))
c=[]
for i in range(n):
	c.append([i+1,b[i]])
	c.sort(key=lambda x:x[1])
ans=0
for i in range(n):
	if(i!=n-1):
		print(c[i][0],end='')
	else:
		print(c[i][0])
for i in range(n):
	ans+=c[i][1]*(n-i-1)
ans/=n
print(f"{
     ans:.2f}")

2.糖果数量有限问题

题目描述
小A有n个糖果盒，第i个盒中有Ai颗糖果，小A每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中的糖果个数之和都不大于x,至少得吃掉几颗糖。
输入格式
输入的第一行是两个用空格隔开的整数，代表糖果盒的个数n和给定的参数x。
第二行有n个用空格隔开的整数，第i个整数代表第i盒糖的糖果个数Ai。
输出格式
输出一行一个整数，代表最少要吃掉的糖果的数量，
思路提醒
此处的贪心策略考虑到的是先不考虑相邻糖盒的糖果数量差异极端的情况，也就是左边很多，右边为零，或右边被吃完后为负的情况，之后再通过if-else结构把这种情况考虑到。
代码展现

n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(n-1):
	if(a[i]+a[i+1]>x):
		temp=a[i]+a[i+1]-x
		ans+=temp
		if(a[