标签:二分答案
4 个条目
-
概念 01 分数规划
在 x_i∈{0,1} 上最大化 Σa_i x_i / Σb_i x_i;参数化权值 a_i-λb_i,把比值判定化为 0/1 优化。
2026-11-12 -
概念 分数规划
把比值优化 max f/g 转化为参数化判定 max(f-λg),用二分答案或 Dinkelbach 求零点。
2026-11-12 -
题目 Earthquake
每条边有成本 c 和时间 t,最大化 (f - Σc) / Σt;二分答案后把边权改为 c + p t,用最小生成树判定。
2026-11-12 -
题目 最小差值生成树
边权极差最小的生成树;排序后滑窗得到加删边区间,二分答案并用时间分治与可撤销并查集判定。
2026-11-10