企业官网建设流程全解析

例题 1：装船问题（蓝桥杯 P532）

题目描述

船载重w，n个货物，每次最多装两件（和<= w）。求最少运输次数。

输入输出

输入：w, n, 然后n个货物重量 输出：最少运输次数

贪心证明

设最轻为a，最重为b。若a + b <= w，则a和任何货都能配对（其他货<= b）。所以a和b配对最优，不浪费a的配对能力。若a + b > w，则b无法和任何货配对，b必须单独运。

完整代码

w=int(input())n=int(input())p=[int(input())for_inrange(n)]p.sort()l,r=0,n-1ans=0whileTrue:ifl==r:ans+=1breakifl>r:breakifp[l]+p[r]<=w:l+=1r-=1ans+=1else:r-=1ans+=1print(ans)

推演过程

w=10, p=[1,2,8,9] 排序: [1,2,8,9] l=0(1), r=3(9): 1+9=10<=10 → 配对, ans=1, l=1,r=2 l=1(2), r=2(8): 2+8=10<=10 → 配对, ans=2, l=2,r=1 l=2>r=1 → 结束 输出: 2 ✓

复杂度

易错点

例题 2：回文判断（蓝桥杯 P1371）

题目描述

判断字符串s是否为回文。

两种写法对比

写法1：切片（简洁但费空间）

s=input()print('Y'ifs==s[::-1]else'N')

写法2：双指针（竞赛推荐，O(1)空间）

s=input()l,r=0,len(s)-1ok='Y'whilel<r:ifs[l]!=s[r]:ok='N'breakl+=1r-=1print(ok)

复杂度对比

例题 3：最小长度子数组（蓝桥杯 P1372）

题目描述

给定数组a和整数s，找和>= s的最短连续子数组长度。

关键细节：左闭右开[l, r)

• r指向下一个待加入的元素
• 区间长度 =r - l，无需+1
• 收缩时total -= a[l]，l += 1，逻辑清晰

完整代码

n,s=map(int,input().split())a=list(map(int,input().split()))min_len=n+1l,r=0,0total=0whilel<n:whiler<nandtotal<s:total+=a[r]r+=1iftotal>=s:min_len=min(min_len,r-l)total-=a[l]l+=1print(min_lenifmin_len<=nelse0)

推演过程（状态表）

n=5, s=7, a=[2,3,1,2,4] 轮次 | l | r | total | 操作 | min_len :---:|:---:|:---:|:---|:---|:---: 初始 | 0 | 0 | 0 | - | 6 1 | 0 | 4 | 8 | 扩到r=3,total=8>=7 | min(6,4)=4 | 1 | 4 | 6 | 减a[0]=2 | - 2 | 1 | 5 | 10 | 扩到r=4,total=10>=7 | min(4,4)=4 | 2 | 5 | 7 | 减a[1]=3 | - 3 | 2 | 5 | 7 | total>=7,不扩 | min(4,3)=3 | 3 | 5 | 6 | 减a[2]=1 | - 4 | 3 | 5 | 6 | r到头 | - | 4 | 5 | 4 | 减a[3]=2 | - 5 | 4 | 5 | 4 | r到头 | - | 5 | 5 | 0 | 减a[4]=4 | 结束 输出: 3 (子数组 [1,2,4])

为什么是 O(n)？

l和r都只往右走，不回退。每个元素被访问两次，总2n次操作。

例题 4：恰好 k 个（蓝桥杯 P1621）—— 重点变形题

题目描述

求有多少个子数组满足：区间中恰好有 k 个数字 >= m。

为什么需要容斥？

直接求"恰好k个"很困难，滑动窗口天然维护"至少"关系。利用容斥：

恰好k个 = 至少k个 - 至少(k+1)个

辅助函数：求"至少k个"

defat_least_k(a,n,m,k):"""求子数组中 >= m 的元素个数至少为 k 的个数"""ifk<=0:returnn*(n+1)//2left,right=0,0cnt=0ans=0whileleft<n:whileright<nandcnt<k:ifa[right]>=m:cnt+=1right+=1ifcnt>=k:ans+=n-right+1else:breakifa[left]>=m:cnt-=1left+=1returnans

主函数

n,m,k=map(int,input().split())a=list(map(int,input().split()))ans=at_least_k(a,n,m,k)-at_least_k(a,n,m,k+1)print(ans)

推演验证

n=5, m=3, k=2, a=[1,3,2,4,3] at_least_k(2): l=0,r=0,cnt=0 扩: r=1,cnt=1; r=2,cnt=1; r=3,cnt=2,r=4 ans+=2 ([0,3],[0,4]), 缩l=1,cnt=2 ans+=2 ([1,3],[1,4]), 缩l=2,cnt=1 扩: r=4,cnt=2,r=5 ans+=1 ([2,4]), 缩l=3,cnt=2 ans+=1 ([3,4]), 缩l=4,cnt=1 扩: cnt=1<2,r=5到头,结束 at_least_k(2) = 6 at_least_k(3): 扩: r=4,cnt=3,r=5 ans+=1 ([0,4]), 缩l=1,cnt=3 ans+=1 ([1,4]), 缩l=2,cnt=2 扩: cnt=2<3,结束 at_least_k(3) = 2 恰好2个 = 6 - 2 = 4 ✓

关键洞察

例题 5：近似 gcd

题目描述

给定数组a和整数g，求有多少个子数组满足：区间内最多只有一个元素不是g的倍数（且长度>= 2）。

思路分析

滑动窗口：维护窗口内"不是g倍数"的元素个数cnt。

• cnt <= 1时窗口合法
• cnt > 1时收缩左边界直到cnt <= 1

统计子数组：对于每个右端点j，以j结尾的合法子数组有j - i个（i为最左合法位置，且长度需>= 2）。

完整代码

n,g=map(int,input().split())a=list(map(int,input().split()))i=0# 左指针cnt=0# 窗口内不是g倍数的元素个数ans=0forjinrange(n):# 右指针ifa[j]%g!=0:cnt+=1# 收缩左边界，直到最多一个不是g的倍数whilecnt>1:ifa[i]%g!=0:cnt-=1i+=1# 以j结尾的合法子数组：从i到j-1开始，共 j-i 个（长度>=2）ifj-i>=1:# 确保子数组长度至少为2ans+=j-iprint(ans)

推演验证

n=5, g=2, a=[1,2,3,4,5] j=0: a[0]=1%2!=0, cnt=1, i=0, j-i=0<1, 不统计 j=1: a[1]=2%2==0, cnt=1, i=0, j-i=1>=1, ans+=1 ([0,1]) j=2: a[2]=3%2!=0, cnt=2, 收缩: i=0,a[0]=1%2!=0,cnt=1,i=1 cnt=1, j-i=1>=1, ans+=1 ([1,2]) j=3: a[3]=4%2==0, cnt=1, i=1, j-i=2>=1, ans+=2 ([1,3],[2,3]) j=4: a[4]=5%2!=0, cnt=2, 收缩: i=1,a[1]=2%2==0,cnt=2; i=2,a[2]=3%2!=0,cnt=1,i=3 cnt=1, j-i=1>=1, ans+=1 ([3,4]) ans = 1+1+2+1 = 5 验证所有长度>=2的子数组: [0,1]=[1,2]: 1不是2倍数 → 1个 ✓ [0,2]=[1,2,3]: 1,3不是 → 2个 ✗ [1,2]=[2,3]: 3不是 → 1个 ✓ [1,3]=[2,3,4]: 3不是 → 1个 ✓ [2,3]=[3,4]: 3不是 → 1个 ✓ [3,4]=[4,5]: 5不是 → 1个 ✓ 共5个 ✓

复杂度分析

例题 6：日志统计（蓝桥杯 P179）

题目描述

小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。每一行的格式是ts id，表示在ts时刻编号id的帖子收到一个"赞"。

如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，就认为该帖子曾是"热帖"。具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内（左闭右开区间）收到不少于K个赞，该帖就曾是"热帖"。

给定日志，统计所有曾是"热帖"的帖子编号，按从小到大顺序输出。

输入格式

N D K ts1 id1 ts2 id2 ... tsN idN

输出格式

每行一个热帖id，按从小到大顺序。

样例

输入：

7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3

输出：

1 3

题解

关键观察：日志按时间排序后，对于每条日志i，以它为右端点，维护一个时间窗口[j, i]使得ts[i] - ts[j] < D。窗口内统计每个id的点赞数。

双指针：i遍历所有日志（右指针），j维护窗口左边界。当ts[i] - ts[j] >= D时，j右移收缩窗口。

input=sys.stdin.readline n,d,k=map(int,input().split())# 读取日志logs=[]for_inrange(n):ts,id=map(int,input().split())logs.append((ts,id))# 按时间排序logs.sort(key=lambdax:x[0])cnt={}# 窗口内每个id的点赞数hot=set()# 热帖集合j=0# 左指针foriinrange(n):# 右指针ts_i,id_i=logs[i]# 当前日志进入窗口cnt[id_i]=cnt.get(id_i,0)+1# 收缩左边界：维护时间窗口 [j, i] 满足 ts[i] - ts[j] < dwhilej<=iandts_i-logs[j][0]>=d:ts_j,id_j=logs[j]cnt[id_j]-=1ifcnt[id_j]==0:delcnt[id_j]j+=1# 判断当前id是否为热帖ifcnt.get(id_i,0)>=k:hot.add(id_i)# 按顺序输出foridinsorted(hot):print(id)

推演过程（可视化）

输入: 7 10 2 日志: [(0,1), (0,10), (9,1), (10,10), (10,1), (100,3), (100,3)] 排序后: [(0,1), (0,10), (9,1), (10,10), (10,1), (100,3), (100,3)] i=0: ts=0, id=1, cnt={1:1} j=0, 0-0=0<10, 不收缩 cnt[1]=1<2, 不是热帖 i=1: ts=0, id=10, cnt={1:1, 10:1} j=0, 0-0=0<10, 不收缩 cnt[10]=1<2, 不是热帖 i=2: ts=9, id=1, cnt={1:2, 10:1} j=0, 9-0=9<10, 不收缩 cnt[1]=2>=2 → hot.add(1) ✓ i=3: ts=10, id=10, cnt={1:2, 10:2} j=0, 10-0=10>=10, 收缩! j=0: 出(0,1), cnt={1:1, 10:2}, j=1 j=1: 10-0=10>=10, 收缩! j=1: 出(0,10), cnt={1:1, 10:1}, j=2 j=2: 10-9=1<10, 停止 cnt[10]=1<2, 不是热帖 (但之前窗口内有2个10，已经被统计过) i=4: ts=10, id=1, cnt={1:2, 10:1} j=2, 10-9=1<10, 不收缩 cnt[1]=2>=2 → hot.add(1) (已在集合中) i=5: ts=100, id=3, cnt={1:2, 10:1, 3:1} j=2, 100-9=91>=10, 大幅收缩... ... 一直收缩到 j=5 j=5: 100-100=0<10, 停止 cnt={3:1}, cnt[3]=1<2, 不是热帖 i=6: ts=100, id=3, cnt={3:2} j=5, 100-100=0<10, 不收缩 cnt[3]=2>=2 → hot.add(3) ✓ 输出: 1, 3 (排序后)

复杂度分析

关键易错点

与例题3（P1372）的对比

📊 今日刷题总结