华为校招&实习机试在线OJ刷题系统 ｜ 在线OJ注册使用教程

目录

题目

思路

Code

题目

题目内容：

大语言模型自回归生成时，历史 token 的 Key 与 Value 会缓存在 KV Cache 里，后面每一步解码直接复用，不必重算。序列越长，KV Cache 占的显存越多，而且是线性增长。

工程上通常先把显存切成一堆等大的块（Block）集中管理，这套机制叫内存池（Memory Pool）：Block 一次分配好，每个 Block 装固定条数 token 的 KV 数据。

## 题目描述

内存池中有 m 个等大的 Block，每个 Block 能容纳 k 条 token 的 KV 数据。

现有 n 个推理请求，第 i 个请求要处理 len[i] 条 token（输入长度与生成长度之和），它占用的 Block 数为 ci = ⌈ len[i] / k ⌉。

决策规则：

- 请求按给定顺序逐个到达。对每个请求可以选择接受或拒绝：

- 接受：被接受请求占用的 Block 总数最终不能超过 m；

- 拒绝：该请求不占用任何资源。

- 允许在后续决策中撤销先前已接受的请求（释放它占用的 Block），以换取更好的整体结果。

- 请求一旦被拒绝，就不能再次考虑。

- 请求之间不允许重排，必须按到达顺序逐个决策。

优化目标：在接受的请求占用 Block 总数不超过 m 的前提下，使被接受的请求数量最多。

## 输入描述

第一行包含三个整数 m、k、n，分别表示内存池中的 Block 总数、每个 Block 可容纳的 token 数量、请求数量。

第二行包含 n 个整数 len[i]，表示第 i 个请求需要处理的 token 数量。

## 输出描述

输出一个整数：最多可接受的请求数量。

样例1

输入：

4 8 3
20 6 11

输出：

2

样例说明：三个请求的 Block 需求依次为 ⌈ 20/8 ⌉ = 3、⌈ 6/8 ⌉ = 1、⌈ 11/8 ⌉ = 2。只接第 1 个请求，它独占 3 个 Block，剩下 1 个 Block 哪个请求都放不下，只能接受 1 个；跳过它、改接第 2 与第 3 个请求，占用 1 + 2 = 3 个 Block，可以接受 2 个。三个请求全接需要 3 + 1 + 2 = 6 个 Block，超过上限 4，所以最多接受 2 个。

> 注：原文未提供输入/输出描述小节，本节格式由官方题解代码（逐 token 读入 m, k, n 后读 n 个 len）推断补全，并与同场次原卷其他来源交叉验证一致。

思路

整体思路：题面说请求按顺序到达、可以撤销已接受的请求，这两条规则合起来说明"顺序"其实不影响结果——任何一个占用总和不超过 m 的请求子集都能被最终选中。所以问题等价于：从 n 个请求里挑尽量多的请求，使它们的 Block 占用之和不超过 m。每个请求的价值都是 1，代价是 c_i = ceil(len[i]/k)，价值相同、代价为正时，从小到大贪心挑选就是最优。

1. 读入 m、k、n，再读入 n 个 len[i]；逐个算出 Block 需求 c_i = (len[i] + k - 1) / k（整数向上取整写法，不能写成整除 len[i]/k，否则余数部分会被丢掉少算一个 Block）。

2. 把所有 c_i 从小到大排序；用 used 记录已占用的 Block 数、ans 记录已接受的请求数，从头开始累加：若 used 加上当前 c_i 仍不超过 m 就接受，否则立即停止——后面只会更大，不可能再放得下。

3. 贪心为什么对：若某个最优解选了 x 个请求但里面有代价更大的请求，可以把它换成未选中的更小代价请求，数量不变、总占用不增；反复替换后，"代价最小的前 x 项之和不超过 m"必然成立，所以从小到大取到第一个放不下的位置就是最大个数。

4. 输出 ans。

复杂度：时间 O(n log n)，瓶颈在排序；计算 c_i 与累加扫描都是 O(n)。n ≤ 10^5 时排序约 10^5 次量级比较，远在时限内。空间 O(n) 存放需求数组。坑点：总和上界约 10^5 × 10^6 = 10^11，累加变量必须用 64 位整数（C/C++/Java 用 long long / long，Go 用 int64），32 位会溢出；"不超过 m"含等号，恰好填满可以接受；不能按到达顺序能放就放——样例 1 里先接 3 个 Block 的请求就会挡住后面两个小请求；也不要写 O(n^2) 的计数背包，n = 10^5 时必然超时。

Code

C++

#include <bits/stdc++.h>
using namespace std;

// 计算最多能接受多少个推理请求
// m 是 Block 总数，k 是每个 Block 能装的 token 数，lens 是各请求的 token 长度
// 返回最多可接受的请求数量
long long solve(long long m, long long k, vector<long long>& lens) {
    vector<long long> need;
    need.reserve(lens.size());
    for (long long x : lens) {
        // 每个请求的 Block 需求：向上取整，不能写成 x / k（会丢掉余数）
        need.push_back((x + k - 1) / k);
    }
    // 需求量从小到大排序：每个请求价值相同，先装最便宜的一定不会更差
    sort(need.begin(), need.end());
    long long used = 0;   // 已占用的 Block 数
    long long ans = 0;    // 已接受的请求数
    for (long long b : need) {
        // 第一次放不下就停止：后面的需求只会更大
        if (used + b > m) break;
        used += b;
        ans++;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long m, k, n;
    cin >> m >> k >> n;
    vector<long long> lens(n);
    for (auto& x : lens) cin >> x;
    cout << solve(m, k, lens) << "\n";
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    // 计算最多能接受多少个推理请求
    // m 是 Block 总数，k 是每个 Block 能装的 token 数，lens 是各请求的 token 长度
    // 返回最多可接受的请求数量
    static long solve(long m, long k, long[] lens) {
        long[] need = new long[lens.length];
        for (int i = 0; i < lens.length; i++) {
            // 每个请求的 Block 需求：向上取整，不能写成 lens[i] / k（会丢掉余数）
            need[i] = (lens[i] + k - 1) / k;
        }
        // 需求量从小到大排序：每个请求价值相同，先装最便宜的一定不会更差
        Arrays.sort(need);
        long used = 0;   // 已占用的 Block 数
        long ans = 0;    // 已接受的请求数
        for (long b : need) {
            // 第一次放不下就停止：后面的需求只会更大
            if (used + b > m) break;
            used += b;
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        // 用 StreamTokenizer 读大输入比 Scanner 快得多，也不会有读取模式切换错位的问题
        java.util.StreamTokenizer in = new java.util.StreamTokenizer(
                new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        long m = (long) in.nval;
        in.nextToken();
        long k = (long) in.nval;
        in.nextToken();
        int n = (int) in.nval;
        long[] lens = new long[n];
        for (int i = 0; i < n; i++) {
            in.nextToken();
            lens[i] = (long) in.nval;
        }
        System.out.println(solve(m, k, lens));
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

// 计算最多能接受多少个推理请求
// m 是 Block 总数，k 是每个 Block 能装的 token 数，lens 是各请求的 token 长度
// 返回最多可接受的请求数量
func solve(m, k int64, lens []int64) int64 {
	need := make([]int64, len(lens))
	for i, x := range lens {
		// 每个请求的 Block 需求：向上取整，不能写成 x / k（会丢掉余数）
		need[i] = (x + k - 1) / k
	}
	// 需求量从小到大排序：每个请求价值相同，先装最便宜的一定不会更差
	sort.Slice(need, func(a, b int) bool { return need[a] < need[b] })
	var used int64 // 已占用的 Block 数
	var ans int64  // 已接受的请求数
	for _, b := range need {
		// 第一次放不下就停止：后面的需求只会更大
		if used+b > m {
			break
		}
		used += b
		ans++
	}
	return ans
}

func main() {
	// bufio.Scanner 默认缓冲区对大输入不够，必须显式扩大缓冲
	reader := bufio.NewReaderSize(os.Stdin, 1024*1024)
	var m, k, n int64
	if _, err := fmt.Fscan(reader, &m, &k, &n); err != nil {
		return
	}
	lens := make([]int64, n)
	for i := int64(0); i < n; i++ {
		fmt.Fscan(reader, &lens[i])
	}
	fmt.Println(solve(m, k, lens))
}

C

#include <stdio.h>
#include <stdlib.h>

// qsort 的比较函数：按 Block 需求从小到大排
// 返回值用 (x > y) - (x < y)，避免直接相减在 64 位大数下溢出 int
static int cmp(const void* a, const void* b) {
    long long x = *(const long long*)a, y = *(const long long*)b;
    return (x > y) - (x < y);
}

// 计算最多能接受多少个推理请求
// m 是 Block 总数，k 是每个 Block 能装的 token 数
// lens 指向各请求的 token 长度数组，n 是请求个数
// 返回最多可接受的请求数量
long long solve(long long m, long long k, const long long* lens, long long n) {
    long long* need = (long long*)malloc(sizeof(long long) * n);
    for (long long i = 0; i < n; i++) {
        // 每个请求的 Block 需求：向上取整，不能写成 lens[i] / k（会丢掉余数）
        need[i] = (lens[i] + k - 1) / k;
    }
    // 需求量从小到大排序
    qsort(need, n, sizeof(long long), cmp);
    long long used = 0;   // 已占用的 Block 数
    long long ans = 0;    // 已接受的请求数
    for (long long i = 0; i < n; i++) {
        // 第一次放不下就停止：后面的需求只会更大
        if (used + need[i] > m) break;
        used += need[i];
        ans++;
    }
    free(need);
    return ans;
}

int main(void) {
    long long m, k, n;
    if (scanf("%lld %lld %lld", &m, &k, &n) != 3) return 0;
    long long* lens = (long long*)malloc(sizeof(long long) * n);
    for (long long i = 0; i < n; i++) scanf("%lld", &lens[i]);
    printf("%lld\n", solve(m, k, lens, n));
    free(lens);
    return 0;
}

Python

import sys


def solve(m, k, lens):
    # 计算最多能接受多少个推理请求
    # 参数 m 是 Block 总数，k 是每个 Block 能装的 token 数，lens 是每个请求的 token 长度
    # 返回值：最多可接受的请求数量
    # 每个请求的 Block 需求：向上取整；(x + k - 1) // k 是整数写法，不能写 x // k
    need = [(x + k - 1) // k for x in lens]
    # 需求量从小到大排序：每个请求价值都一样（都是 1），先装最便宜的一定不会更差
    need.sort()
    used = 0   # 已占用的 Block 数
    ans = 0    # 已接受的请求数
    for b in need:
        # 第一次放不下就停止：后面的需求只会更大，不可能再放得下
        if used + b > m:
            break
        used += b
        ans += 1
    return ans


def main():
    data = sys.stdin.buffer.read().split()
    # 前三个数是 Block 总数 m、每个 Block 容量 k、请求数 n
    m = int(data[0])
    k = int(data[1])
    n = int(data[2])
    # 之后 n 个数是每个请求的 token 长度
    lens = [int(x) for x in data[3:3 + n]]
    print(solve(m, k, lens))


main()