T30204: 小P的LLM推理加速

greedy, http://cs101.openjudge.cn/practice/30204/

随着大语言模型参数量的爆炸式增长，边缘设备上的推理效率成为了研究热点。小P的团队正在为一款搭载了新型 NPU（神经网络处理单元）的嵌入式设备开发推理框架。该 NPU 采用了一种特殊的双缓冲机制来管理显存与计算单元的数据交互。

该 NPU 包含 n 个异构的计算核，编号为 1 到 n。由于硬件架构的特性，每个计算核在执行连续的推理任务时，其能耗会呈现周期性变化。

具体来说，对于第 i（1 ≤ i ≤ n）个计算核，其数据加载与计算遵循“冷-热”交替模式：

第 1 个 推理周期（冷启动）：需要从主存加载权重，能耗为 xi 焦耳。
第 2 个 推理周期（热运行）：权重已在缓存中，直接计算，能耗为 yi 焦耳。
第 3 个 推理周期（强制刷新）：由于双缓冲队列的限制，缓存被新的数据流覆盖，需要重新加载，能耗变回 xi 焦耳。
第 4 个 推理周期（热运行）：能耗再次变为 yi 焦耳。
以此类推

设备的电池总能量预算为 m 焦耳。作为框架的调度算法设计者，你的任务并不关心具体使用了哪些计算核，而是要通过合理分配任务，使得在电量耗尽前，设备总共能完成的 推理周期数最大化。

输入

输入的第一行包含两个正整数 n 和 m，分别代表计算核的数量和电池的总能量预算。

输入的第 i+1 行（1 ≤ i ≤ n）包含两个正整数 xi 和 yi，分别表示第 i 个计算核在“冷启动”“热运行”状态下的能耗。

输出

输出一行一个非负整数，表示 m 焦耳能量预算下，所有计算核累计能完成的最大推理周期总数。

样例输入

2 10
4 1
3 3

样例输出

提示

贪心

【数据范围】

对于所有测试数据，均有： - 1 <= n <= 10^5； - 1 <= m <= 10^{18}； - 对于所有 1 <= i <= n，均有 1 <= xi, yi <= 10^9。

数据可能具有下面两种特殊性质，也可能没有: 特殊性质 A：对于所有 1 <= i <= n，均有 xi = yi。

特殊性质 B：对于所有 1 <= i <= n，均有 xi >= yi。

来源

TA-xjk, https://www.luogu.com.cn/problem/P14635

P14635 [NOIP2025] 糖果店 / candy（官方数据）
https://www.luogu.com.cn/problem/P14635
小 X 开了一家糖果店，售卖 $n$ 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 $i$ ( $1 \leq i \leq n$ ) 种糖果，购买第一颗的价格为 $x_{i}$ 元，第二颗为 $y_{i}$ 元，第三颗又变回 $x_{i}$ 元，第四颗则为 $y_{i}$ 元，以此类推。
小 R 带了 $m$ 元钱买糖果。小 R 不关心糖果的种类，只想得到数量尽可能多的糖果。你需要帮助小 R 求出， $m$ 元钱能购买的糖果数量的最大值。
输入格式
输入的第一行包含两个正整数 $n, m$ ，代表糖果的种类数和小 R 的钱数。
输入的第 $i + 1$ ( $1 \leq i \leq n$ ) 行包含两个正整数 $x_{i}, y_{i}$ ，分别表示购买第 $i$ 种糖果时第奇数颗的价格和第偶数颗的价格。
输出格式
输出一行一个非负整数，表示 $m$ 元钱能购买的糖果数量的最大值。
样例
输入 #1
2 10
4 1
3 3
输出 #1
4
输入 #2
3 15
1 7
2 3
3 1
输出 #2
8
说明/提示
【样例 1 解释】
小 R 可以购买 4 颗第一种糖果，共花费 $4 + 1 + 4 + 1 = 10$ 元。
【样例 2 解释】
小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 $1 + 2 + 12 = 15$ 元。
【数据范围】
对于所有测试数据，均有：
$1 \leq n \leq 10^{5}$ ；
$1 \leq m \leq 10^{18}$ ；
对于所有 $1 \leq i \leq n$ ，均有 $1 \leq x_{i}, y_{i} \leq 10^{9}$ 。

【尹显齐 25 物理学院】思路：取每一种糖果的过程，都可以分解成取或不取 $x_{i}$ + 取 $n$ 个 $x_{i} + y_{i}$ 的过程。对于所有的 $x_{i} + y_{i}$ ，肯定取其中最小的是最优的。对于所有的 $x_{i}$ ，取不同个数都对应着不同情况，所以只要枚举取的 $x_{i}$ 的个数就可以，并且对于取 $k$ 个 $x_{i}$ 的情况，一定是取最小的前 $k$ 个最优，所以排序+前缀和即可。

python

n,m = map(int,input().split())
nums = []
s = []
for i in range(n):
    x,y = map(int,input().split())
    nums.append(x)
    s.append(x+y)
minsum = min(s)
ans = 0
nums.sort()
pre = [0]
for ni in nums:
    pre.append(pre[-1]+ni)
for i,p in enumerate(pre):
    ans = max(ans,((m-p)//minsum)*2+i)
print(ans)

这里还有一个略快的做法：在上一个方法的基础上继续贪心，我们将 $x_{i}$ 有序排列，假设 $m$ 是足够大的（不足够大的话策略显然），现在我们用bisect_left插入 $\frac{min (x_{i} + y_{i})}{2}$ ，它变成了第 $k$ 个数。那么最优解一定是取 $x_{i}$ 的前 $n$ 个数，其中 $n$ 只可能等于 $k - 2$ ， $k - 1$ ， $k$ 。证明： $x_{k} + x_{k + 1} \geq min (x_{i} + y_{i}) > x_{k - 1} + x_{k - 2}$ ，所以 $n > k$ 和 $n < k - 2$ 都不可能更优。

所以只需要对 $k$ 个数排序就行了。

python

n,m = map(int,input().split())
nums = []
s = []
for i in range(n):
    x,y = list(map(int,input().split()))
    s.append(x+y)
    nums.append(x)
minsum = min(s)
ans = 0
pre = []
mini = 10**10
for i in range(n):
    if nums[i]*2 < minsum:
        pre.append(nums[i])
    else:
        mini = min(mini,nums[i])
pre.sort()
for p in pre:
    m -= p
    if m < 0:
        break
    ans += 1
ans += m//minsum*2
m -= (m//minsum)*minsum
if (pre and m >= minsum-pre[-1]) or m >= mini:
    ans += 1
print(ans)

OJ数据疑似过于水。

python

import sys

def solve():
    # 使用 sys.stdin 读取所有输入，处理大数据量时更快
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        n = int(next(iterator))
        m = int(next(iterator))
    except StopIteration:
        return

    # 读取糖果数据
    # 存储格式: [(x1, y1), (x2, y2), ...]
    candies = []
    for _ in range(n):
        x = int(next(iterator))
        y = int(next(iterator))
        candies.append((x, y))

    # 1. 找到“主力糖果” (best)
    # 标准：x+y 最小。如果 x+y 相同，则 x 越小越好（因为剩下的零钱更容易买到第一颗）
    min_s = float('inf')
    best_idx = -1

    for i in range(n):
        current_s = candies[i][0] + candies[i][1]
        if current_s < min_s:
            min_s = current_s
            best_idx = i
        elif current_s == min_s:
            # 如果总和相同，选 x 更小的
            if candies[i][0] < candies[best_idx][0]:
                best_idx = i
    
    best_x, best_y = candies[best_idx]
    best_s = best_x + best_y

    # 2. 收集其他种类的第一颗糖果价格 (singles)
    singles = []
    for i in range(n):
        if i == best_idx:
            continue
        singles.append(candies[i][0])
    
    # 排序，以便贪心地选取便宜的单颗
    singles.sort()

    max_count = 0
    
    # 3. 枚举策略：先计算完全不买其他单颗的情况 (k=0)
    # 计算主力糖果能买多少
    # 剩余钱能买几对 * 2
    count_from_best = (m // best_s) * 2
    rem_m = m % best_s
    # 如果剩余钱够买主力糖果的第一颗
    if rem_m >= best_x:
        count_from_best += 1
    
    max_count = count_from_best

    # 4. 枚举购买 k 个其他单颗糖果的情况
    current_spent = 0
    for k in range(len(singles)):
        # 买第 k+1 便宜的单颗
        current_spent += singles[k]
        
        # 如果钱不够了，提前结束
        if current_spent > m:
            break
        
        # 剩余预算
        rem_m = m - current_spent
        
        # 用剩余预算买主力糖果
        # 能买多少对
        pairs = rem_m // best_s
        cnt = pairs * 2
        
        # 买完对后剩下的零钱
        leftover = rem_m % best_s
        # 够不够买主力的单颗
        if leftover >= best_x:
            cnt += 1
        
        # 总数量 = 已买的 k+1 个单颗 + 主力糖果数量
        total_candies = (k + 1) + cnt
        
        if total_candies > max_count:
            max_count = total_candies

    print(max_count)

if __name__ == '__main__':
    solve()

T30204: 小P的LLM推理加速 ​

T30204: 小P的LLM推理加速