当前位置：首页 > news >正文

【Python蓝桥杯备赛宝典】

news 来源：原创 2025/7/10 12:25:00

文章目录

一、基础数据结构
- 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.接水时间最短问题
  - 2.糖果数量有限问题
  - 3.分发时间最短问题
  - 4.采摘苹果最多问题
三、搜索
- 3.1 BFS和DFS基础
- 3.2 剪枝
- 3.3 洪水填充
- 3.4 BFS与最短路径
- 3.5 双向广搜
- 3.6 BFS和优先队列
- 3.7BFS与双端队列
四、高级数据结构
- 4.1 并查集
- 4.2 树状数组
- 4.3 线段树
- *4.4 可持久化线段树
- *4.5 分块与莫队算法
- - 1.连连看问题
- *4.6 块状链表
- *4.7 简单树上问题
- *4.8 LCA
五、动态规划
- 5.1 DP概念和编程方法
- 5.2 经典线性DP问题
- 5.3 数位统计DP
- 5.4 压缩状态DP
- - 1.松散子序列
- 5.5 区间DP
- *5.6 树形DP
- 5.7 一般优化
- 5.8 单调队列优化

一、基础数据结构

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=</