1101Div2-贪心/排序+前缀和+DP+三分搜索
1101Div2-贪心/排序+前缀和+DP+三分搜索
Dashboard - Codeforces Round 1101 (Div. 2) - Codeforces
Easy：A
Mid：B
Hard：C1、C2
A
题意：
有n个人分散在不同的位置，他的目的是让所有人都在同一个地方；
可以执行以下操作：每次选两个人，让他们在各自当前位置之间的某个整数位置见面
求最小的操作次数；
题解：
题解思路是，将位置进行排序，依次选择最右边和最左边的两个人，让他们在中间的某个位置见面；当所有剩余位置都相同时停止；
for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) a.sort() ans = 0 l, r = 0, n - 1 while l < r and a[l] != a[r]: ans += 1 l += 1 r -= 1 print(ans)#include <stdio.h>#include <stdlib.h>int cmp(const void *a, const void *b) { return (*(int*)a - *(int*)b);}
int main() { int t; scanf("%d", &t);
while (t--) { int n; scanf("%d", &n);
int a[100]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); }
qsort(a, n, sizeof(int), cmp);
int ans = 0; int l = 0, r = n - 1;
while (l < r && a[l] != a[r]) { ans++; l++; r--; }
printf("%d\n", ans); }
return 0;}B
题意：
有一个长为n的蛋糕，每个位置i上的高度为ai，可执行如下操作：
将刀放在某个高度h处，从左到右扫描，如果该位置蛋糕的高度大于h，超出的部分会被推到i+1位置上，位置n上的超出部分完全脱离蛋糕
目标是对于每个位置i，只考虑前i个位置，通过上述操作能使高度达到的最大平整高度是对少？
题解：
遍历数组，计算前缀和，对于每个位置i，计算前缀平均值cur/(i+1)，维护最小的前缀平均值，第i个答案就是前i个位置的前缀平均值的最小值
for _ in range(int(input())): ans = [] n = int(input()) a = list(map(int,input().split())) cur = 0 mi = float('inf') for i,x in enumerate(a): cur += x if cur//(i+1) < mi: mi = cur//(i+1) ans.append(mi) print(*ans)#include<stdio.h>
int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); int a[200000]; for(int i = 0;i < n;i++){ scanf("%d",&a[i]); } long long cur = 0; long long mi = 1e18; for(int i = 0;i < n;i++){ cur += a[i]; long long ave = cur/(i+1); if(ave < mi){ mi = ave; } printf("%lld ",mi); } printf("\n"); } return 0;}C1-DP
Alice有n个朋友排队入场，派对上有x张桌子，每张桌子有s个座位。每个朋友有三种性格类型：
- I（内向型）：必须坐在一张完全空的桌子旁
- E（外向型）：必须坐在已经有人的桌子旁 （非空桌）
- A（中间型）：可以坐在任何桌子旁
朋友按固定顺序入场，Alice必须为每个人立即分配座位或拒绝入场。一旦入座就不能再移动。目标是最多能让多少人入座。
-
贪心+枚举
A型可以灵活选择，前
m个A型朋友当作I型处理，剩余当作E枚举当前有多少个A型当作E处理，模拟的过程如下： 1.维护以入座人数
ans，和已使用桌子数2.I型：若
T<t，就占用一张桌子3.E型：若当前入座人数小于总容量
ans<T*s，就可以入座4.A型：前
m个当作I型，其余当作E枚举所有可能的
m，求出最大的入座人数贪心+枚举 def f(S,m,t,s):T = 0ans = 0for c in S:if c == "I":if T < t:T += 1ans += 1elif c == "E":if ans < T*s:ans += 1else:if m > 0:m -= 1if T < t:T += 1ans += 1else:if ans < T*s:ans += 1return ansfor _ in range(int(input())):n,t,s = map(int,input().split())S = input().strip()r = S.count("A")ans = 0for i in range(r + 1):ans = max(ans,f(S,i,t,s))print(ans) -
DP
一、状态设计
我们只需要追踪两个关键信息：
- 多少张桌子被占用了（至少有1人的桌子数）
- 总共入座了多少人 这两个信息足够我们判断：
- I型能否入座：看是否还有空桌（j < x）
- E型能否入座：看是否有非空桌（j > 0）且还有空位（seated < j*s） 状态定义
dp[i][j] = 处理完前i个人后，恰好有j张桌子被占用时，最大入座人数i：自然维度，表示处理到第几个人j：关键约束维度。桌子数有限，且I型必须开新桌，所以桌子占用数是核心瓶颈- 值存储”最大入座人数”：在相同(i,j)下，入座人数越多越好，因为多一个人就多一个满足条件的机会（尤其是对E型，需要有人坐在桌旁）
- i：0到n（最多3000）
- j：0到x（最多3000）
- 总共最多9×10^6个状态 二、初始化与最终答案
dp[0][0] = 0 # 初始状态：0个人，0张桌子被占用，入座0人# 其他状态初始化为-1（不可达）三、状态转移方程
对于第i个人（字符为c），已知前i-1人的状态dp[i-1][j] = seated：
基础操作：拒绝
dp[i][j] = max(dp[i][j], seated)拒绝永远可行，桌子占用数和入座人数都不变。
Case 1: I型（内向者）
只能开新桌，否则拒之门外：
if j < x: # 还有空桌dp[i][j+1] = max(dp[i][j+1], seated + 1)- 桌子占用数+1
- 入座人数+1 Case 2: E型（外向者） 只能坐非空桌，需要两个条件：
if j > 0 and seated < j * s: # 有非空桌且有剩余座位dp[i][j] = max(dp[i][j], seated + 1)j > 0：至少有一张桌子被占用（存在非空桌）seated < j * s：已入座人数 < 这些桌子的总容量（还有空位） 为什么不需要知道具体哪张桌有空位？ 贪心性质：只要seated < j*s，就一定有至少一张桌子未满。因为j张桌子总容量为j*s，人数少于总容量，根据鸽巢原理，至少有一张桌子有空位。
Case 3: A型（中间者）
两种选择，取最优：
# 选择1: 当作I型，开新桌if j < x:dp[i][j+1] = max(dp[i][j+1], seated + 1)# 选择2: 当作E型，坐非空桌if j > 0 and seated < j * s:dp[i][j] = max(dp[i][j], seated + 1)A型的灵活性体现在这里——DP自动选择能导致更优最终结果的选项。
ans = max(dp[n]) # 处理完所有人后，取所有可能桌子占用数下的最大入座人数DP t = int(input())for _ in range(t):n, x, s = map(int, input().split())S = input().strip()dp = [[-1] * (x + 1) for _ in range(n + 1)]dp[0][0] = 0for i in range(1, n + 1):c = S[i - 1]for j in range(x + 1):if dp[i - 1][j] == -1:continueseated = dp[i - 1][j]# 拒绝当前人（总是可选）dp[i][j] = max(dp[i][j], seated)if c == 'I':# 必须坐空桌：需要有空桌子if j < x:dp[i][j + 1] = max(dp[i][j + 1], seated + 1)elif c == 'E':# 必须坐非空桌：# 条件1: 有非空桌 (j > 0)# 条件2: 非空桌还有空位 (seated < j*s)if j > 0 and seated < j * s:dp[i][j] = max(dp[i][j], seated + 1)else:# 选项1: 开新桌if j < x:dp[i][j + 1] = max(dp[i][j + 1], seated + 1)# 选项2: 坐非空桌if j > 0 and seated < j * s:dp[i][j] = max(dp[i][j], seated + 1)ans = max(dp[n])print(ans)
C2-三分搜索
-
思路(DS)
一、问题的本质
这道题的核心决策是：将多少个A型朋友当作I型处理？
设这个数量为
m（前m个A型当I型，其余当E型），定义函数：f(m) = 按照这个策略能入座的最大人数问题转化为：在
m ∈ [0, A_count]上求f(m)的最大值。二、为什么
f(m)是单峰函数？直观理解
想象两个极端：
m = 0（所有A型都当E型）：
- 桌子全靠I型来开
- 如果I型很少，桌子开得少，后面E型和A型没桌子可坐
- 问题：桌子太少，座位不够****m = A_count（所有A型都当I型）：
- 大量A型开新桌，很快就用完所有桌子
- 后面真正的I型没桌子可坐，只能被拒绝
- 问题：桌子被A型浪费，真正的I型无法入座****最优的m在中间：平衡桌子使用，既不让桌子太少导致E型无处可坐，也不让桌子被A型过早耗尽导致I型无法入座。 单调性分析
当m从0逐渐增加到A_count时：
阶段1：上升阶段（m较小）
m=0: A型都当E型I型开桌 → 只有几张桌子A型和E型争抢非空桌的座位问题：桌子太少，很多人因无非空桌而被拒绝m=1: 第1个A型开新桌多了一张桌子 → 更多非空桌 → 更多人能入座f(1) > f(0)m=2: 第2个A型开新桌再多一张桌子 → 更多人能入座f(2) > f(1)为什么上升？ 增加m意味着更多A型开新桌，增加桌子数量，为E型和后续A型创造更多”非空桌”座位。此时桌子还没用完，利大于弊。
阶段2：下降阶段（m较大）
m接近A_count: 大部分A型都开新桌桌子很快被占满m=A_count-1: 倒数第2个A型还在开新桌可能已经用完所有桌子m=A_count: 所有A型都开新桌桌子被A型占满，后面的I型没桌子可坐f(A_count) < f(A_count-1)为什么下降？ 增加m导致桌子被A型过早占满，真正的I型（必须坐空桌）无法入座。此时弊大于利。
数学证明思路
考虑相邻两个值
f(m)和f(m+1)：差异：第m+1个A型从”当E型”变为”当I型”
- 正面效果：可能多开一张桌子，增加T → 后续E型和A型更容易入座
- 负面效果：消耗一张空桌 → 后续I型可能无法入座 随着m增大：
- 正面效果递减（桌子越来越多，但总桌子数有限）
- 负面效果递增（剩余空桌越来越少，I型越难入座）
因此存在一个临界点，超过后
f(m+1) < f(m)，形成单峰。 三、为什么能用二分搜索？
二分搜索的前提是：函数具有单调性。
但
f(m)不是单调的（先增后减），怎么二分？关键技巧：比较相邻值判断方向
不需要
f(m)整体单调，只需要能判断当前在上升还是下降阶段：if f(m) < f(m + 1):# 还在上升，最大值在右侧# 可以安全排除 m 及左侧else:# 已经开始下降，最大值在左侧或就是m# 可以安全排除 m+1 及右侧这就是三分搜索的二分实现，专门用于单峰函数求极值。
import sysinput = sys.stdin.readlineT = int(input())for _ in range(T): n, t, s = map(int, input().split()) S = input().strip() def f(m): T = 0 ans = 0 remaining = m for c in S: if c == 'I': if T < t: T += 1 ans += 1 elif c == 'E': if ans < T * s: ans += 1 else: if remaining > 0: remaining -= 1 if T < t: T += 1 ans += 1 else: if ans < T * s: ans += 1 return ans A_count = S.count('A') l = -1 r = A_count while l + 1 < r: mid = (l + r) // 2 # 比较 mid 和 mid+1 if f(mid) < f(mid + 1): # 上升阶段，最大值在 mid+1 或更右 l = mid else: # 下降阶段，最大值在 mid 或更左 r = mid print(f(r))