AI Agent 管理
P6088. AI Agent 管理
场次:2026年10月23日-非AI方向 · 来源:CodeFun2000 P6088
题目描述
小华平时要带着 名 AI Agent 一起赶一个项目。项目规模按代码行来计,一共是 行 Loc。他打算把这些行数拆给不同的 AI Agent,并让自己用来交代任务的时间尽量短。
AI Agent 听得懂自然语言。小华把需求讲完,再交由它去完成。
一名 AI Agent 好不好用,由下面三个量决定:
委托效率:小华对着这名 AI Agent 讲需求、对齐方案时,它每分钟能消化并记住的代码行数,记作 行每分钟。
最低消费:模型调用的费用由小华自己付。为了吃到便宜套餐,一旦启用这名 AI Agent,购买时长不能短于 分钟。
最高消费:各家模型单价不同,小华给每名 AI Agent 卡了花费上限,购买时长不能长于 分钟。
再补三条:
小华在意的是自己何时能把任务全部交代完、从而空出手,并不在意项目最终哪一天收尾。所以各名 AI Agent 谁先谁后都无所谓。
交互效率保持不变,多出来的额度可以闲置。已购买的套餐能覆盖的代码行数达到 行即可。
同一时刻小华只能跟一名 AI Agent 交谈,任务得一个一个交代。
请给出购买方案,使这些套餐覆盖的行数不少于 ,并且购买分钟数之和最小。输出这个最小的分钟数。
输入格式
第一行是两个整数 和 。 表示 AI Agent 有几名, 表示项目一共有多少行 Loc。
其后 行,每一行三个整数 、、。这三个数按顺序对应该名 AI Agent 的委托效率、它的最低消费,以及它的最高消费。
数据范围:
输出格式
输出一个整数,表示覆盖全部行数所需购买分钟数的最小值。若把每名 AI Agent 都买到最高消费仍不够,则输出 。
示例
示例 1
输入:
2 20000
9000 3 8
4000 2 6输出:
3说明: 效率 的那名至少买 分钟,得到 行,已经盖过 行,用时 分钟。另一名要买满 分钟才够 行。因此最少是 分钟。
示例 2
输入:
2 30000
8000 1 2
5000 1 2输出:
-1说明: 两名都买到顶时,覆盖行数是 ,仍小于 ,所以输出 。
示例 3
输入:
3 74000
9000 6 6
8000 5 5
7000 5 5输出:
10说明:
只启用效率 与 :分钟 ,行数 。
只启用效率 与 :分钟 ,行数 。
分钟已经够用,而且比 分钟更短。
解题思路
输出到底是什么:分钟数之和,而不是「最晚交付时刻」
题面里有两句容易被读成两件不同的事:
- 「同一时刻只能跟一名 AI Agent 交谈,任务得一个一个交代」—— 说明这些分钟数是排队串起来的,总时长就是各人购买分钟数的和;
- 「多出来的额度可以闲置,覆盖的行数达到 行即可」—— 说明约束是不少于 ,不要求正好等于,也不要求把额度用满。
于是问题可以完整地写成:为每名 Agent 选一个分钟数 ,满足
表示不启用这名 Agent(不花钱、不产出);一旦启用就必须买够 分钟,最多买到 分钟。注意 与 都是分钟数,不是行数 —— 覆盖的行数是 。
顺便就能得到 的判据:把所有 Agent 都买到上限,能覆盖的最大行数是 ;这个和都小于 时,任何方案都不可能达标。
为什么「按效率从高到低买」不够:最低消费是一整块成本
如果每名 Agent 都能任意买 0 分钟以上,这题就是分数背包:每分钟换 行,把 从大到小排好,前面的买满、最后一名补零头即可。
问题出在 上:启用一名 Agent 不是「买一分钟」,而是「买至少一整块」。看这组数据:
2 250000
2000 1 100
1800 1000 1000按效率贪心:先买效率 的那名,买满 分钟得 行、花 分钟;还差 行,第二名需要 分钟,但它的最低消费是 ,只能买 分钟,总计 分钟。
而最优解是只启用第二名: 行,花 分钟。。
效率更高的那名反而把总时长推上去了 —— 因为它贡献的那 行本来就不需要,而第二名无论如何都要付满 分钟。这种「够用了,但还得多付一整块」的结构,使得选择哪几名启用、每名买多少,必须一起决定,不能从左到右贪心。
状态设计:分钟数是天然的背包容量
把「总共买多少分钟」当作背包容量: 就是总分钟数,而每名 Agent 提供的是一个区间选项 —— 0 分钟,或者 里任一分钟数。
记 dp[j] = 恰好花 分钟时,能覆盖的最大行数。初始 dp[0] = 0(一分钟不买,覆盖 0 行),其余用 表示「这个分钟数凑不出来」。
dp = [-1] * (T + 1)
dp[0] = 0
for e, u, v in agents:
ndp = dp[:] # 第一支:不启用这一名
for j in range(u, T + 1): # 第二支:启用,买 x 分钟
for x in range(u, min(v, j) + 1):
if dp[j - x] >= 0:
ndp[j] = max(ndp[j], dp[j - x] + e * x)
dp = ndpT 是分钟数的上界:答案不会超过任何一个已知可行方案的分钟数,所以取一个可行解的分钟数当上界就够了(下一节会说怎么拿到一个尽量小的上界)。
这里有两个容易写错的地方:
-1表示「凑不出来」,不是「覆盖 0 行」。若用0当哨兵,dp[j-x] >= 0就永远为真,一个凑不出来的分钟数会被当成合法状态继续转移,最后可能输出一个并不存在的方案;- 转移是
max而不是赋值:同一个j可能由不同的x到达,也可能由「不启用这一名」到达。
把内层循环换成滑动窗口最大值
上面的转移对每个 j 都要试 种 x,,乘上 和 之后不可接受。
把下标改写一下:令 ,则 ,
对固定的 j 来说, 是常数,要最大化的只有 ,而 的范围是
一个随 j 平移的窗口。于是用单调队列维护窗口内 的最大值,每个 j 均摊 :
from collections import deque
for e, u, v in agents:
ndp = dp[:] # 不启用这一名
dq = deque() # 存 (k, dp[k] - e*k),值单调递减
for j in range(u, T + 1):
k = j - u # 窗口右端新进入的下标
if dp[k] >= 0:
val = dp[k] - e * k
while dq and dq[-1][1] <= val:
dq.pop()
dq.append((k, val))
while dq and dq[0][0] < j - v: # 窗口左端滑出
dq.popleft()
if dq:
ndp[j] = max(ndp[j], dq[0][1] + e * j)
dp = ndp上界、下界与 :让 T 尽量小
- 下界:任何方案每分钟最多产出 行,所以 。若某个可行解恰好等于这个下界,它必然是最小值,可以直接返回 —— 这一步能把大量数据挡在 DP 之前。
- 上界:先造几个可行解,取最小的那个当
T。最保底的一个是「全部买满」,它的分钟数是 ;再补两个更紧的:按效率从高到低依次买(够 就停)、只启用某一名。 - : 时无解。注意这个判断要在用上界之前做,否则「买满」这个方案本身就不可行。
if sum(e * v for e, _, v in agents) < G:
print(-1)
return
lb = (G + emax - 1) // emax # 下界
best = sum(v for _, _, v in agents) # 买满:一定可行,故可当上界
... # 用两个启发式把 best 压小
if best == lb:
print(best)
return只要 best 是真实可行的(覆盖行数确实 ),把它当上界就是安全的:DP 只算到 T = best,答案若比它更小一定落在数组里,若一样大则 best 本身就是答案。
实现落点
dp[0] = 0:一分钟也不买的状态是合法起点;if u > best: continue:这名 Agent 的最低消费已经超过总预算,启用它不可能更优,直接跳过(否则内层窗口的右端k = j-u永远取不到值);hi = min(v, best)与k >= j - hi:窗口左端用的是被上界裁剪过的v,与数组长度保持一致;- 入队前判
dp[k] >= 0:凑不出来的分钟数不能参与转移; - 答案是「最小的
j使dp[j] >= G」,是>=而不是==—— 覆盖行数超出 完全合法。
完整代码实现
"""
P6088. AI Agent 管理 - 按分钟数背包 + 单调队列
C 名 AI Agent,第 t 名的委托效率为 e_t 行/分钟,最低消费 u_t 分钟、
最高消费 v_t 分钟。若启用第 t 名,购买分钟数 x_t 必须满足
u_t <= x_t <= v_t;不启用则为 0。要求 sum(e_t * x_t) >= G,
最小化 sum(x_t)。全部买到上限仍不够时输出 -1。
输入格式:
- 首行两个整数 C、G;
- 随后 C 行,每行 e_t、u_t、v_t。
输出格式:
- 一个整数:最小购买分钟数之和;无解输出 -1。
核心思路:
dp[j] = 恰好花 j 分钟能覆盖的最大行数,dp[0] = 0,其余 -1(凑不出来)。
每名 Agent 提供两种转移:不启用;启用并买 x ∈ [u, v] 分钟。
把 dp[j-x] + e*x 改写成 (dp[k] - e*k) + e*j(k = j-x),窗口
k ∈ [j-v, j-u] 上的最大值用单调队列维护,单次转移均摊 O(1)。
上界取一个已知可行解的分钟数,下界取 ceil(G / max(e)),相等即可提前返回。
时间复杂度:O(C * T),T 为已知可行解的分钟数上界
空间复杂度:O(T)
"""
# https://codefun2000.com/p/P6088
import sys
from collections import deque
# @sample-start
"""
样例输入 1:
2 20000
9000 3 8
4000 2 6
样例输出 1:
3
"""
# @sample-end
# @sample-start
"""
样例输入 2:
2 30000
8000 1 2
5000 1 2
样例输出 2:
-1
"""
# @sample-end
# @sample-start
"""
样例输入 3:
3 74000
9000 6 6
8000 5 5
7000 5 5
样例输出 3:
10
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
c = int(data[0])
g = int(data[1])
agents = []
p = 2
for _ in range(c):
e = int(data[p])
u = int(data[p + 1])
v = int(data[p + 2])
p += 3
agents.append((e, u, v))
if g <= 0:
print(0)
return
# 全部买到上限仍不够 -> 无解
if sum(e * v for e, _, v in agents) < g:
print(-1)
return
emax = max(e for e, _, _ in agents)
lb = (g + emax - 1) // emax # 效率最高的那名连轴转:下界
# 上界:先取「全部买满」(一定可行),再用启发式压小
best = sum(v for _, _, v in agents)
lines = cost = 0
for e, u, v in sorted(agents, key=lambda t: -t[0]): # 按效率从高到低买
if lines >= g:
break
x = max(u, min(v, (g - lines + e - 1) // e))
lines += e * x
cost += x
if lines >= g:
best = min(best, cost)
for e, u, v in agents: # 只启用一名
if e * v >= g:
best = min(best, max(u, (g + e - 1) // e))
if best == lb: # 撞上下界,就是答案
print(best)
return
# dp[j] = 恰好花 j 分钟能覆盖的最大行数;-1 表示凑不出来
dp = [-1] * (best + 1)
dp[0] = 0
for e, u, v in agents:
if u > best: # 最低消费已超预算,启用没有意义
continue
hi = min(v, best)
ndp = dp[:] # 不启用这一名
dq = deque() # (k, dp[k] - e*k),值单调递减
for j in range(u, best + 1):
k = j - u
if dp[k] >= 0:
val = dp[k] - e * k
while dq and dq[-1][1] <= val:
dq.pop()
dq.append((k, val))
while dq and dq[0][0] < j - hi: # 窗口左端滑出
dq.popleft()
if dq:
cand = dq[0][1] + e * j
if cand > ndp[j]:
ndp[j] = cand
dp = ndp
ans = best
for j in range(best + 1):
if dp[j] >= g: # 达到 G 行即可,允许超出
ans = j
break
print(ans)
def run_tests():
"""运行嵌入的示例,方便本地自测。"""
import io
cases = [
("2 20000\n9000 3 8\n4000 2 6\n", "3"),
("2 30000\n8000 1 2\n5000 1 2\n", "-1"),
("3 74000\n9000 6 6\n8000 5 5\n7000 5 5\n", "10"),
# 只看效率贪心会得出 1100,正解是只用第二名
("2 250000\n2000 1 100\n1800 1000 1000\n", "1000"),
# 最低消费必须满足:不能说 2 分钟够 2000 行
("2 2000\n1000 3 8\n500 1 100\n", "3"),
# 买多少分钟可以取区间内的任意值,不是只有 u 或 v
("1 10000\n1000 1 100\n", "10"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected!r}, 实际={output!r} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:,,两名分别是 与
先看单名能不能扛下来。
- 第一名:覆盖 行需要 分钟,落在 内,合法,花费 分钟,实际覆盖 行;
- 第二名:需要 分钟,落在 内,合法,花费 分钟,覆盖 行。
两者取小,答案 。
下界也正好是 : ,任何方案每分钟最多覆盖 行,要 行至少需要 分钟。上界 、下界 ,答案是 。代码里这一步走的是 best == lb 的提前返回分支。
把 DP 的思路也走一遍(上界取 ),dp[j] 是「恰好花 分钟覆盖的最大行数」:
| 分钟 | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| 只有第一名( 分钟) | |||||||||
| 再加上第二名( 分钟) |
第二张表里 只能是「不启用第一名、第二名买 2 分钟」; 两种走法(第一名 3 分钟,或第二名 3 分钟给 行)取大,仍是 。第一个满足 的 是 ,与前面的结论一致。
示例 3:三名都只能整块买时,目标仍然是「分钟数之和最小」
示例 3 里三名都是 ,只能整块买。三种两两组合的分钟数是 、、,第三种( 与 )覆盖 ,所以答案是 —— 尽管它的「效率之和」低于另外两种组合。分钟数之和最小与覆盖行数最大,本来就是两个不同的目标。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举每名的购买时长 | 、,组合数无法承受 | ||
| 按分钟背包 + 枚举转移 | 每个 还要试 种买法 | ||
| 按分钟背包 + 单调队列(最优) | 窗口最大值均摊 , 为可行解的分钟数上界 |
不是一个固定的 (那是 的上限):代码先造一个可行解把它压下来,常见情况下它接近 ,而这一档如果恰好可行,连 DP 都不会进。
易错点总结
1. 按效率从高到低贪心,忽略「整块」成本
写成「把 排序,前面的买满、最后一名补零头」时,每名都按 x = max(u, ceil(need/e)) 补到最低消费,看起来照顾到了 ,但它仍然会为一整块用不上的时长付钱。输入
2 250000
2000 1 100
1800 1000 1000贪心输出 (效率 的买满 分钟,效率 的再买 分钟),正解是只启用第二名、花 分钟。
2. 买入分钟数忘了取 max(u, ...)
只按 ceil(need / e) 算需要多少分钟,没有和最低消费取大。输入
2 2000
1000 3 8
500 1 100第一名被算成 分钟( 行),但它的最低消费是 , 分钟根本买不到,正确答案是 。这一类错误的输出总是偏小,而且样例 1 恰好因为 而看不出来。
3. 只考虑「买到最低消费」或「买满」两种时长
把每名的候选时长收成 三种(这在 的示例 3 上完全正确),就丢掉了区间内部的取值。输入 1 10000 配 1000 1 100:真正需要的是 分钟( 行),候选里只有 分钟( 行,不够)与 分钟( 行),于是输出 ,正确值是 。DP 的内层窗口之所以要扫整个 ,正是为了这一类「买够就行、不必买满」的情况。