四季读书网
四季读书网

【笔试突围】4月2日网易真题解析+在线刷题

四季读书网 2 0
【笔试突围】4月2日网易真题解析+在线刷题
【笔试突围】4月2日网易真题解析+在线刷题 第1张

🔗刷题网址: bishipass.com

27届实习提前批秋招汇总，持续更新，建议收藏，欢迎分享https://docs.qq.com/smartsheet/DRHVEc05MbE5CYUZa?tab=sc_JGxFAj

网易-2026.04.02

题目一：边境排阵

看起来是田忌赛马换皮，本质就是“最多能赢几场”。把双方战力排序后，用最小可行的己方单位去吃掉当前最弱的对手，最后检查最大胜场是否严格超过一半。

难度：Low

题目二：背包格整理

先按题目给的三层关键字排序，再把每个物品按“行优先、列次之”的规则塞进网格。难点不在算法，而在把放置规则翻译成稳定的逐格扫描。

难度：Mid

题目三：索桥火炮清场

真正的关键不是模拟每一炮，而是反过来问：打了  炮之后，哪些坐标组无论怎么推都不可能被边界淘汰。那些还卡在中间的坐标组只能靠直接命中解决，于是可以二分答案。

难度：Mid

题目四：贴图驻留调度

整题就是按规则做状态机。只要先看透“同一贴图当前已加载 mip 始终是一段连续后缀，且过期时间一致”，实现就能收敛到按贴图维护 minMip + expire + usedVRAM 的模拟。

难度：High

1. 边境排阵

问题描述

边境演练开始后，对手已经提前公开了这一轮的出阵顺序。

一共会进行  轮对抗。第  轮里，对手会派出一支战力为  的小队。你手里也有  支小队，它们的战力分别是 ，并且每支小队只能出战一次。

每轮规则如下：

  • >
    如果你派出的小队战力严格大于对手，这一轮记为你方获胜。
  • >
    如果双方战力相同，或者你方更小，都算你方失利。

你可以自由安排己方  支小队的出战顺序。请判断，是否存在一种安排方式，使得最终你方的胜场数严格大于败场数。

保证  是奇数。

输入格式

第一行输入一个整数 ，表示测试数据组数。

对于每组数据：

  • >
    第一行输入一个奇数 ，表示双方小队数量。
  • >
    第二行输入  个整数 ，表示己方小队战力。
  • >
    第三行输入  个整数 ，表示对手按出战顺序给出的战力。

输出格式

对于每组数据输出一行：

  • >
    若可以做到胜场数严格大于败场数，输出 YES。
  • >
    否则输出 NO。

样例输入

2
5
2 5 7 1 6
3 5 6 2 7
3
3 3 3
3 3 3

样例输出

YES
NO

数据范围

  • >
  • >
  • >
     为奇数
  • >
  • >
    所有测试数据中， 的总和不超过 
样例
解释说明
样例 1
第一组可以把己方战力排成一种更优的对位方式，最终拿到超过一半的胜场，所以输出 YES。第二组所有人战力都相同，而平局也算失利，因此不可能赢过对手。

题解

题目真正要问的是：己方最多能赢多少场。

只要最大胜场数都不超过 ，那就不可能让胜场严格大于败场；反过来，如果最大胜场数大于 ，答案就是 YES。

所以核心只剩一句话：

  • >
    怎么求“最多能赢几场”。

这就是标准的贪心配对。

先把己方战力数组和对手战力数组都从小到大排序。随后用一个指针 j 指向当前还没有被击败的最弱对手：

  • >
    依次查看排好序的己方战力 a。
  • >
    如果当前这支队伍 a[i] 能击败 b[j]，就让它去拿下这一分，然后 j 往后移动。
  • >
    如果 a[i] 连当前最弱的 b[j] 都打不过，那么它拿去对别的对手也不会更好，直接放弃这支队伍，继续看下一支更强的己方队伍。

为什么这个贪心是对的？

  • >
    如果某支己方队伍已经可以赢下当前最弱的可击败对手，那就没有必要把它浪费到更强的对手身上。
  • >
    让它吃掉当前最弱的那一个，能把更强的己方队伍留给后面更难啃的对手。
  • >
    如果它连当前最弱的都赢不了，那它无论换谁都不可能拿分，跳过不会损失最优解。

因此，这个过程统计出来的胜场数就是最大胜场数。

最后因为  是奇数，所以“胜场严格大于败场”恰好等价于：

直接判断即可。

#复杂度分析

  • >
    排序复杂度是 。
  • >
    双指针线性扫描复杂度是 。

所以单组数据总复杂度为 ，空间复杂度为 。在所有测试数据总规模不超过  的条件下完全可以通过。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()


defmax_win(a, b):
# 排序后，始终尝试用当前最小的可行己方战力去击败最弱的未击败对手。
    a.sort()
    b.sort()

    j = 0
    win = 0
    n = len(a)

for x in a:
# 只有严格大于时才算获胜。
if j < n and x > b[j]:
            win += 1
            j += 1

return win


defsolve():
    t = int(input())
    out = []

for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        win = max_win(a, b)
        out.append("YES"if win > n // 2else"NO")

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<algorithm>
#include<iostream>
#include<vector>
usingnamespacestd;

intmaxWin(vector<longlong>& a, vector<longlong>& b){
// 贪心原则：用最小的可行己方战力去吃掉当前最弱的可击败对手。
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

int n = static_cast<int>(a.size());
int j = 0;
int win = 0;

for (longlong x : a) {
if (j < n && x > b[j]) {
            ++win;
            ++j;
        }
    }

return win;
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;
while (t--) {
int n;
cin >> n;

vector<longlong> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
        }
for (int i = 0; i < n; ++i) {
cin >> b[i];
        }

int win = maxWin(a, b);
cout << (win > n / 2 ? "YES" : "NO") << '\n';
    }
return0;
}
  • >
    Java
import java.io.InputStream;
import java.util.Arrays;

publicclassMain{
privatestaticintmaxWin(long[] a, long[] b){
// 先排序，再做一次双指针统计最大胜场。
        Arrays.sort(a);
        Arrays.sort(b);

int j = 0;
int win = 0;
int n = a.length;

for (long x : a) {
if (j < n && x > b[j]) {
                win++;
                j++;
            }
        }
return win;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();

int t = fs.nextInt();
while (t-- > 0) {
int n = fs.nextInt();
long[] a = newlong[n];
long[] b = newlong[n];

for (int i = 0; i < n; i++) {
                a[i] = fs.nextLong();
            }
for (int i = 0; i < n; i++) {
                b[i] = fs.nextLong();
            }

int win = maxWin(a, b);
            sb.append(win > n / 2 ? "YES" : "NO").append('\n');
        }

        System.out.print(sb);
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

privateintread()throws Exception {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

longnextLong()throws Exception {
int c;
do {
                c = read();
            } while (c <= 32);

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long val = 0;
while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
return val * sign;
        }

intnextInt()throws Exception {
return (int) nextLong();
        }
    }
}

2. 背包格整理

问题描述

LYA 在整理一个带网格的仓库背包。

背包一共有  行  列，行号从上到下递增，列号从左到右递增。现在有  个物品，需要先按固定规则排序，再按顺序依次尝试放入背包。

每个物品都有下面这些属性：

  • >
    id：物品唯一编号，所有物品的 id 互不相同。
  • >
    height、width：物品占用的高和宽，不能旋转。
  • >
    quality：品质，数值越大越优先。
  • >
    type：类别，只会是 equip、weapon、item、other 之一。

排序规则如下：

  1. 先按 type 排序，优先级为 equip > weapon > item > other。
  2. 若 type 相同，则 quality 更高的排在前面。
  3. 若前两项都相同，则 id 更小的排在前面。

放置规则如下：

  • >
    按排好序后的顺序，一个一个尝试放入背包。
  • >
    对于当前物品，优先选择行号最小的可行位置；如果同一行里有多个可行位置，再选列号最小的那个。
  • >
    物品必须完整放进背包，且覆盖区域内所有格子都还为空。
  • >
    如果整个背包都找不到可行位置，就跳过这个物品。

请输出：

  1. 最终是否放下了全部物品。
  2. 最终背包每个格子里放的是哪个物品的 id；若为空则输出 0。

输入格式

第一行输入三个整数 ，分别表示背包的高、宽和物品数量。

接下来  行，每行输入：

id height width quality type

其中 type 只会是 equip、weapon、item、other 之一。

输出格式

第一行输出一个字符串：

  • >
    如果所有物品都成功放入，输出 YES。
  • >
    否则输出 NO。

接下来输出  行，每行  个整数，表示最终背包状态。

样例输入

4 3 3
1 1 3 7 other
2 3 1 2 equip
3 2 2 4 other

样例输出

YES
2 3 3
2 3 3
2 0 0
1 1 1

数据范围

  • >
  • >
  • >
  • >
  • >
  • >
    type 只会在 equip、weapon、item、other 中出现
样例
解释说明
样例 1
排序后，id=2 的装备会最先放入；随后在剩余空位中继续尝试放 id=3 和 id=1，最终三个物品都能放下，所以输出 YES。

题解

这题没有隐藏算法，按题意一步一步模拟就够了。

先做排序。

题目已经给出了三层比较关键字：

  1. type 优先级。
  2. quality 降序。
  3. id 升序。

把每个物品存下来以后，按这个规则排一次序即可。

然后是放置。

对于当前物品，题目要求：

  • >
    行号尽量小。
  • >
    在满足这个前提下，列号尽量小。

这句话直接翻译成程序，就是枚举左上角坐标 (r,c)：

  • >
    r 从上到下扫。
  • >
    c 在当前行里从左到右扫。
  • >
    一旦找到一个可以完整放下的位置，就立刻放进去，不必继续找。

判断一个位置能不能放也很直接：

  • >
    先看物品右边界和下边界会不会越出背包。
  • >
    再检查这个 height × width 矩形里的格子是否全是空格。

如果找到位置，就把这个矩形区域全部写成对应的 id；如果遍历完整个背包都找不到，就说明这个物品放不进去。

最后再看是否所有物品都成功放入：

  • >
    全部成功则输出 YES。
  • >
    只要有一个被跳过，就是 NO。

#复杂度分析

设单个物品大小为 。

  • >
    排序复杂度是 。
  • >
    每个物品最多尝试所有左上角位置，共  个。
  • >
    每次检查位置需要看  个格子，而题目保证 ，这是一个很小的常数。

所以总复杂度可以写成 。在本题范围内完全足够，空间复杂度为 。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()

PRI = {
"equip": 3,
"weapon": 2,
"item": 1,
"other": 0,
}


defcan_put(grid, r, c, h, w):
# 只要矩形里出现一个非 0 格子，这个位置就不能放。
for i in range(r, r + h):
for j in range(c, c + w):
if grid[i][j] != 0:
returnFalse
returnTrue


defput_item(grid, r, c, h, w, item_id):
# 找到可行位置后，把整个占用矩形统一写成当前物品 id。
for i in range(r, r + h):
for j in range(c, c + w):
            grid[i][j] = item_id


defsolve():
    n, m, t = map(int, input().split())
    items = []

for _ in range(t):
        item_id, h, w, q, typ = input().split()
        items.append((int(item_id), int(h), int(w), int(q), typ))

# 先按题目给定规则排序。
    items.sort(key=lambda x: (-PRI[x[4]], -x[3], x[0]))

    grid = [[0] * m for _ in range(n)]
    ok = True

for item_id, h, w, _, _ in items:
        placed = False

for r in range(n - h + 1):
for c in range(m - w + 1):
if can_put(grid, r, c, h, w):
                    put_item(grid, r, c, h, w, item_id)
                    placed = True
break
if placed:
break

ifnot placed:
            ok = False

    print("YES"if ok else"NO")
for row in grid:
        print(*row)


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
usingnamespacestd;

structItem {
int id;
int h;
int w;
int q;
string type;
};

inttypePriority(conststring& type){
if (type == "equip") {
return3;
    }
if (type == "weapon") {
return2;
    }
if (type == "item") {
return1;
    }
return0;
}

boolcanPut(constvector<vector<int>>& grid, int r, int c, int h, int w){
for (int i = r; i < r + h; ++i) {
for (int j = c; j < c + w; ++j) {
if (grid[i][j] != 0) {
returnfalse;
            }
        }
    }
returntrue;
}

voidputItem(vector<vector<int>>& grid, int r, int c, int h, int w, int id){
for (int i = r; i < r + h; ++i) {
for (int j = c; j < c + w; ++j) {
            grid[i][j] = id;
        }
    }
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m, t;
cin >> n >> m >> t;

vector<Item> items(t);
for (int i = 0; i < t; ++i) {
cin >> items[i].id >> items[i].h >> items[i].w >> items[i].q >> items[i].type;
    }

    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
int pa = typePriority(a.type);
int pb = typePriority(b.type);
if (pa != pb) {
return pa > pb;
        }
if (a.q != b.q) {
return a.q > b.q;
        }
return a.id < b.id;
    });

vector<vector<int>> grid(n, vector<int>(m, 0));
bool ok = true;

for (const Item& item : items) {
bool placed = false;

for (int r = 0; r + item.h <= n && !placed; ++r) {
for (int c = 0; c + item.w <= m; ++c) {
if (canPut(grid, r, c, item.h, item.w)) {
                    putItem(grid, r, c, item.h, item.w, item.id);
                    placed = true;
break;
                }
            }
        }

if (!placed) {
            ok = false;
        }
    }

cout << (ok ? "YES" : "NO") << '\n';
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (j) {
cout << ' ';
            }
cout << grid[i][j];
        }
cout << '\n';
    }
return0;
}
  • >
    Java
import java.io.InputStream;
import java.util.Arrays;

publicclassMain{
privatestaticclassItem{
int id;
int h;
int w;
int q;
        String type;
    }

privatestaticinttypePriority(String type){
if ("equip".equals(type)) {
return3;
        }
if ("weapon".equals(type)) {
return2;
        }
if ("item".equals(type)) {
return1;
        }
return0;
    }

privatestaticbooleancanPut(int[][] grid, int r, int c, int h, int w){
for (int i = r; i < r + h; i++) {
for (int j = c; j < c + w; j++) {
if (grid[i][j] != 0) {
returnfalse;
                }
            }
        }
returntrue;
    }

privatestaticvoidputItem(int[][] grid, int r, int c, int h, int w, int id){
for (int i = r; i < r + h; i++) {
for (int j = c; j < c + w; j++) {
                grid[i][j] = id;
            }
        }
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);

int n = fs.nextInt();
int m = fs.nextInt();
int t = fs.nextInt();

        Item[] items = new Item[t];
for (int i = 0; i < t; i++) {
            Item item = new Item();
            item.id = fs.nextInt();
            item.h = fs.nextInt();
            item.w = fs.nextInt();
            item.q = fs.nextInt();
            item.type = fs.next();
            items[i] = item;
        }

        Arrays.sort(items, (a, b) -> {
int pa = typePriority(a.type);
int pb = typePriority(b.type);
if (pa != pb) {
return pb - pa;
            }
if (a.q != b.q) {
return b.q - a.q;
            }
return a.id - b.id;
        });

int[][] grid = newint[n][m];
boolean ok = true;

for (Item item : items) {
boolean placed = false;

for (int r = 0; r + item.h <= n && !placed; r++) {
for (int c = 0; c + item.w <= m; c++) {
if (canPut(grid, r, c, item.h, item.w)) {
                        putItem(grid, r, c, item.h, item.w, item.id);
                        placed = true;
break;
                    }
                }
            }

if (!placed) {
                ok = false;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(ok ? "YES" : "NO").append('\n');
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j > 0) {
                    sb.append(' ');
                }
                sb.append(grid[i][j]);
            }
            sb.append('\n');
        }

        System.out.print(sb);
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

privateintread()throws Exception {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

String next()throws Exception {
int c;
do {
                c = read();
            } while (c <= 32);

            StringBuilder sb = new StringBuilder();
while (c > 32) {
                sb.append((char) c);
                c = read();
            }
return sb.toString();
        }

longnextLong()throws Exception {
int c;
do {
                c = read();
            } while (c <= 32);

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long val = 0;
while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
return val * sign;
        }

intnextInt()throws Exception {
return (int) nextLong();
        }
    }
}

3. 索桥火炮清场

问题描述

一座索桥的安全区对应开区间 。

桥上现在还有  名敌人，他们的坐标分别为 ，满足 。不同敌人可以站在同一个坐标上。

你每次可以朝某个整数坐标  开一炮，效果如下：

  • >
    若敌人的当前坐标恰好等于 ，则该敌人会被直接淘汰。
  • >
    若敌人的当前坐标小于 ，则会被向左击退  个单位。
  • >
    若敌人的当前坐标大于 ，则会被向右击退  个单位。

当敌人的坐标变成  或  时，会立刻掉出安全区并被淘汰。

每次开火前，你都可以根据当前剩余敌人的位置重新选择新的落点。

请计算，至少需要开多少炮，才能把所有敌人全部淘汰。

输入格式

第一行输入三个整数 ，分别表示敌人数、安全区长度和每次击退距离。

第二行输入  个整数 ，表示敌人的初始坐标。

输出格式

输出一个整数，表示最少需要开火的次数。

样例输入

3 10 2
3 5 9

样例输出

2

数据范围

  • >
  • >
  • >
  • >
样例
解释说明
样例 1
第一次把炮落在坐标 5，可以直接命中坐标 5 的敌人，同时把 3 推到 1，把 9 推到 11 并淘汰。第二次再开一炮，就能把坐标 1 的敌人清掉。

题解

这题如果直接模拟“每一炮该打哪里”，会非常绕。

真正好用的做法是反过来想：

  • >
    假设总共只允许开  炮。
  • >
    哪些敌人一定能靠边界被推死？
  • >
    哪些敌人无论怎么推，都必须被直接命中？

只要这个判定能做出来，就可以二分答案。

#1. 打了  炮之后，哪些位置一定推不出去

先看某个初始坐标为  的敌人。

如果想把它向左推出去，那么每一炮都必须落在它的右边。这样它总共最多只会被向左推  次，也就是最多左移 。

所以：

  • >
    若 ，那它有可能靠一直向左推被淘汰。
  • >
    若 ，那即使每一炮都往左推，它也仍然留在安全区内。

同理：

  • >
    若 ，那它有可能靠一直向右推被淘汰。
  • >
    若 ，那即使每一炮都往右推，它也仍然留在安全区内。

于是，所有落在这个开区间里的坐标：

都不可能只靠边界击退被清掉。

这部分敌人只能靠“炮点正好打在它当前坐标上”来解决。

#2. 中间这部分只需要按“不同坐标”计数

题目允许多名敌人站在同一个位置。

如果炮点正好打在这个坐标上，那么这个坐标上的所有敌人都会同时满足“当前坐标恰好为 ”，也会一起被淘汰。

所以对必须直接命中的这部分敌人，只需要统计：

  • >
    有多少个不同的坐标组还卡在中间。

如果这部分不同坐标的数量大于 ，那就不可能在  炮内全部直接点掉。

#3. 为什么这个条件也足够

设中间还剩下的不同坐标组共有 mid 个，并且 mid <= k。

这时可以这样做：

  • >
    每一炮都选在某个还没被点掉的中间坐标组上。
  • >
    这样该坐标组会被直接清掉。
  • >
    它左边的所有敌人都会再向左推一次。
  • >
    它右边的所有敌人都会再向右推一次。

也就是说：

  • >
    原本已经满足  的左侧敌人，在这  炮里可以累计得到足够多的左推次数，最终一定会出界。
  • >
    原本已经满足  的右侧敌人，也会累计得到足够多的右推次数，最终一定会出界。
  • >
    中间坐标组则被逐个直接点掉。

所以判定条件就是：

  • >
    中间不同坐标组数量 <= k 时， 炮可行。

#4. 二分答案

随着  增大：

  • >
    区间  会越来越小。
  • >
    中间必须直接命中的坐标组数量只会减少，不会增加。

因此这个判定具有单调性，可以对  二分。

把所有坐标排序并去重后，对于某个给定的 ：

  • >
    左边界是 k * r
  • >
    右边界是 L - k * r
  • >
    需要统计有多少个去重后的坐标严格落在这两个值之间

这可以用二分查找在有序数组上  完成。

#复杂度分析

  • >
    先排序去重，复杂度是 。
  • >
    二分答案的次数是 。
  • >
    每次判定只做两次二分查找，复杂度是 。

所以总复杂度为 ，空间复杂度为 。

参考代码

  • >
    Python
import sys
from bisect import bisect_left, bisect_right

input = lambda: sys.stdin.readline().strip()


defsolve():
    n, L, r = map(int, input().split())
    xs = list(map(int, input().split()))

# 同一坐标上的敌人可以一炮一起清掉，所以判定时只需要看不同坐标。
    pos = sorted(set(xs))

# 当 k 足够大时，中间区间一定会缩空。
    hi = (L - 1 + r - 1) // r
    lo = 0

defok(k):
        left = k * r
        right = L - k * r

# 统计严格落在 (left, right) 里的不同坐标数量。
        l = bisect_right(pos, left)
        rr = bisect_left(pos, right)
        mid = rr - l
return mid <= k

while lo < hi:
        mid = (lo + hi) // 2
if ok(mid):
            hi = mid
else:
            lo = mid + 1

    print(lo)


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<algorithm>
#include<iostream>
#include<vector>
usingnamespacestd;

boolok(constvector<longlong>& pos, longlong L, longlong r, longlong k){
longlong left = k * r;
longlong right = L - k * r;

auto itL = upper_bound(pos.begin(), pos.end(), left);
auto itR = lower_bound(pos.begin(), pos.end(), right);
longlong mid = itR - itL;
return mid <= k;
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
longlong L, r;
cin >> n >> L >> r;

vector<longlong> xs(n);
for (int i = 0; i < n; ++i) {
cin >> xs[i];
    }

    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

longlong lo = 0;
longlong hi = (L - 1 + r - 1) / r;

while (lo < hi) {
longlong mid = (lo + hi) / 2;
if (ok(xs, L, r, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

cout << lo << '\n';
return0;
}
  • >
    Java
import java.io.InputStream;
import java.util.Arrays;

publicclassMain{
privatestaticintlowerBound(long[] arr, int len, long target){
int l = 0;
int r = len;
while (l < r) {
int m = (l + r) >>> 1;
if (arr[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
return l;
    }

privatestaticintupperBound(long[] arr, int len, long target){
int l = 0;
int r = len;
while (l < r) {
int m = (l + r) >>> 1;
if (arr[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
return l;
    }

privatestaticbooleanok(long[] pos, int len, long L, long r, long k){
long left = k * r;
long right = L - k * r;

int l = upperBound(pos, len, left);
int rr = lowerBound(pos, len, right);
long mid = rr - l;
return mid <= k;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);

int n = fs.nextInt();
long L = fs.nextLong();
long r = fs.nextLong();

long[] xs = newlong[n];
for (int i = 0; i < n; i++) {
            xs[i] = fs.nextLong();
        }

        Arrays.sort(xs);
long[] pos = newlong[n];
int len = 0;
for (long x : xs) {
if (len == 0 || pos[len - 1] != x) {
                pos[len++] = x;
            }
        }

long lo = 0;
long hi = (L - 1 + r - 1) / r;
while (lo < hi) {
long mid = (lo + hi) >>> 1;
if (ok(pos, len, L, r, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        System.out.println(lo);
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

privateintread()throws Exception {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

longnextLong()throws Exception {
int c;
do {
                c = read();
            } while (c <= 32);

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long val = 0;
while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
return val * sign;
        }

intnextInt()throws Exception {
return (int) nextLong();
        }
    }
}

4. 贴图驻留调度

问题描述

某个渲染系统用贴图流式加载来管理显存，显存上限为 。

每张贴图都有唯一编号 id，并且包含 mip0 到 mip(c-1) 共 c 级。其中：

  • >
    mip0 的显存占用为 
  • >
    对于 ，mip i 的显存占用为 mip(i-1) 的 
  • >
    题目保证所有级别的显存占用都是整数

现在会给出按时间顺序排列的若干操作，时间 t 非递减。

#加载请求

若某次操作为：

t id X s c

表示在时刻  请求贴图 id 的 mipX。

此时系统需要保证 mipX, mip(X+1), ..., mip(c-1) 都处于已加载状态。

规则如下：

  1. 新加载的这些资源，其过期时间设为 。
  2. 加载时间为闭区间 ，也就是说在当前时刻  只有当 expire < u 时，资源才算真正过期、允许被卸载。
  3. 若该贴图本来就已经加载了一部分，只补装还没加载的 mip，并把当前已加载的 mip 过期时间一起更新为 。
  4. 若本次请求依赖的 mip 当前已经加载，则这些依赖资源在本次请求处理过程中即使已经过期，也不能被 LRU 回收。

#显存不足时的 LRU 回收

若加载时显存不足，则系统会尝试回收已过期资源：

  • >
    按过期时间从小到大回收。
  • >
    若过期时间相同，则按贴图 id 从小到大回收。
  • >
    同一贴图里，过期时间相同的 mip 必须整体一起卸载，并记一条日志。
  • >
    若当前请求依赖某些 mip，则这些 mip 即使过期，也不能在这次 LRU 中被回收。

如果把所有可回收资源都卸载以后，显存仍然不够，那么本次加载失败，并且不更新任何过期时间。

#主动清理

若某次操作为：

t -1

表示在时刻  主动清理所有当前已经过期的资源。

此时的卸载顺序不按 LRU，而是按贴图 id 从小到大依次卸载。

#日志规则

只有当某张贴图的加载状态真的发生变化时，才输出一条日志：

t id minMip usedVRAM

其中：

  • >
    minMip 表示该贴图变化后当前最小的已加载 mip 编号
  • >
    如果该贴图被完全卸载，则输出 -1
  • >
    usedVRAM 表示本次变化后系统当前已使用的显存

输入格式

第一行输入三个整数 ，分别表示显存上限、过期持续时间和操作数量。

接下来  行，每行是下面两种格式之一：

  • >
    t id X s c
  • >
    t -1

对于同一个 id，输入保证对应的 s 和 c 始终相同。

输出格式

按照题意要求输出所有日志。

样例输入

120 4 7
1 3 0 20 1
1 2 0 40 2
1 1 0 40 2
1 4 0 20 1
5 4 0 20 1
6 4 0 20 1
99 -1

样例输出

1 3 0 20
1 2 0 70
1 1 0 120
6 1 -1 70
6 4 0 90
99 2 -1 40
99 3 -1 20
99 4 -1 0

数据范围

  • >
  • >
  • >
  • >
  • >
    输入时间 t 非递减
样例
解释说明
样例 1
前三次请求正好把显存占满，后两次对贴图 4 的尝试里，t=5 时原资源还处于闭区间加载期，不能卸载；到 t=6 时才真正过期，于是按 LRU 顺序先卸掉贴图 1，再成功加载贴图 4。

题解

这题规则很多，但真正写代码前，先看清两个不变量，整个实现会简单很多。

#1. 同一贴图当前已加载的 mip 一定是一段连续后缀

请求 mipX 时，必须保证：

  • >
    mipX, mip(X+1), ..., mip(c-1) 都已加载

如果之前已经加载了一部分，只会“往更小的编号补装缺失层”，不会把已有的更高编号层拆掉。

所以任意时刻，一张贴图的已加载集合一定长成：

也就是说，只要维护当前最小已加载层 minMip 就够了。

#2. 同一贴图当前已加载的 mip 过期时间始终一致

每次请求成功时：

  • >
    新补装的层过期时间设成 
  • >
    当前已加载的层也全部更新成 

因此一张贴图当前还留在显存里的所有 mip，过期时间总是同一个值。

这意味着：

  • >
    LRU 回收时，可以把一整张贴图当成一个回收单元。
  • >
    主动清理时，也是一整张贴图一起卸载。

所以每张贴图只需要维护下面这些信息：

  • >
    minMip：当前最小已加载层，若完全未加载则记为 -1
  • >
    expire：当前整张贴图的统一过期时间
  • >
    suffixSize[minMip]：从 minMip 到 c-1 的总显存占用

#3. 怎样处理一次加载请求

假设当前请求是 (t, id, X, s, c)。

先算这次真正还需要补多少显存：

  • >
    如果这张贴图完全没加载过，需要补整个后缀 X..c-1
  • >
    如果已经加载到 minMip，而且 X < minMip，只需要补 X..minMip-1
  • >
    如果 X >= minMip，说明请求依赖的层本来就已经都在，不需要额外显存

如果显存不够，就开始按 LRU 回收：

  • >
    只能回收 expire < t 的贴图
  • >
    回收顺序按 (expire, id) 升序
  • >
    当前请求涉及的这张贴图，如果它已经有依赖层在显存里，那么整张贴图都不能在本次 LRU 中被回收

如果把所有可回收贴图都删掉后仍然不够：

  • >
    本次请求失败
  • >
    并且不能刷新过期时间

如果请求成功：

  • >
    需要补装时更新 minMip
  • >
    不管是否补装，都把当前贴图的 expire 刷成 t + D
  • >
    只有 minMip 真的变了，才输出加载日志

#4. 怎样处理主动清理

主动清理不看 LRU 顺序，而是：

  • >
    把所有 expire < t 的贴图按 id 从小到大依次卸掉

每卸一张贴图，都要立刻输出一条日志。

#5. 复杂度分析

设当前参与过的贴图数为 。

由于 ，直接在每次请求时把可回收贴图收集出来排序即可：

  • >
    单次请求最坏复杂度 
  • >
    主动清理复杂度 

在本题规模下完全够用，实现也更稳。

参考代码

  • >
    Python
import sys

input = lambda: sys.stdin.readline().strip()


classTexture:
def__init__(self, base, cnt):
        self.cnt = cnt
        self.suf = [0] * (cnt + 1)
        level = [0] * cnt
        level[0] = base
for i in range(1, cnt):
            level[i] = level[i - 1] // 4
for i in range(cnt - 1, -1, -1):
            self.suf[i] = self.suf[i + 1] + level[i]

        self.min_mip = -1
        self.expire = -1

defused_size(self):
if self.min_mip == -1:
return0
return self.suf[self.min_mip]

defextra_size(self, need_mip):
if self.min_mip == -1:
return self.suf[need_mip]
if need_mip < self.min_mip:
return self.suf[need_mip] - self.suf[self.min_mip]
return0


defsolve():
    M, D, N = map(int, input().split())
    tex = {}
    used = 0
    out = []

deflog_state(t, tex_id, min_mip):
        out.append(f"{t}{tex_id}{min_mip}{used}")

for _ in range(N):
        parts = input().split()
        t = int(parts[0])
        tex_id = int(parts[1])

if tex_id == -1:
# 主动清理：按 id 从小到大卸载所有当前已过期贴图。
for cur_id in sorted(tex.keys()):
                cur = tex[cur_id]
if cur.min_mip != -1and cur.expire < t:
                    used -= cur.used_size()
                    cur.min_mip = -1
                    cur.expire = -1
                    log_state(t, cur_id, -1)
continue

        need_mip = int(parts[2])
        base = int(parts[3])
        cnt = int(parts[4])

if tex_id notin tex:
            tex[tex_id] = Texture(base, cnt)
        cur = tex[tex_id]

        add = cur.extra_size(need_mip)

if used + add > M:
# LRU：只允许回收真正过期的贴图，并且按 (expire, id) 升序。
            cand = []
for other_id, other in tex.items():
if other.min_mip == -1:
continue
if other.expire >= t:
continue
# 当前请求依赖的贴图若已经在显存里，本次不能回收它。
if other_id == tex_id:
continue
                cand.append((other.expire, other_id))

            cand.sort()

for _, other_id in cand:
if used + add <= M:
break
                other = tex[other_id]
                used -= other.used_size()
                other.min_mip = -1
                other.expire = -1
                log_state(t, other_id, -1)

if used + add > M:
# 失败时不能刷新过期时间。
continue

        changed = False
if cur.min_mip == -1:
            used += cur.suf[need_mip]
            cur.min_mip = need_mip
            changed = True
elif need_mip < cur.min_mip:
            used += cur.suf[need_mip] - cur.suf[cur.min_mip]
            cur.min_mip = need_mip
            changed = True

        cur.expire = t + D
if changed:
            log_state(t, tex_id, cur.min_mip)

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()
  • >
    Cpp
#include<algorithm>
#include<iostream>
#include<string>
#include<tuple>
#include<unordered_map>
#include<vector>
usingnamespacestd;

structTexture {
vector<longlong> suf;
int minMip = -1;
longlong expire = -1;

    Texture() = default;

    Texture(longlong base, int cnt) {
vector<longlong> level(cnt, 0);
        level[0] = base;
for (int i = 1; i < cnt; ++i) {
            level[i] = level[i - 1] / 4;
        }

        suf.assign(cnt + 1, 0);
for (int i = cnt - 1; i >= 0; --i) {
            suf[i] = suf[i + 1] + level[i];
        }
    }

longlongusedSize()const{
if (minMip == -1) {
return0;
        }
return suf[minMip];
    }

longlongextraSize(int needMip)const{
if (minMip == -1) {
return suf[needMip];
        }
if (needMip < minMip) {
return suf[needMip] - suf[minMip];
        }
return0;
    }
};

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

longlong M, D;
int N;
cin >> M >> D >> N;

unordered_map<int, Texture> tex;
vector<string> logs;
longlong used = 0;

auto addLog = [&](longlong t, int id, int minMip) {
        logs.push_back(to_string(t) + " " + to_string(id) + " " + to_string(minMip) +
" " + to_string(used));
    };

for (int step = 0; step < N; ++step) {
longlong t;
int id;
cin >> t >> id;

if (id == -1) {
vector<int> ids;
            ids.reserve(tex.size());
for (constauto& [key, _] : tex) {
                ids.push_back(key);
            }
            sort(ids.begin(), ids.end());

for (int curId : ids) {
                Texture& cur = tex[curId];
if (cur.minMip != -1 && cur.expire < t) {
                    used -= cur.usedSize();
                    cur.minMip = -1;
                    cur.expire = -1;
                    addLog(t, curId, -1);
                }
            }
continue;
        }

int needMip, cnt;
longlong base;
cin >> needMip >> base >> cnt;

if (!tex.count(id)) {
            tex[id] = Texture(base, cnt);
        }
        Texture& cur = tex[id];
longlong add = cur.extraSize(needMip);

if (used + add > M) {
vector<pair<longlong, int>> cand;
            cand.reserve(tex.size());

for (constauto& [otherId, other] : tex) {
if (other.minMip == -1) {
continue;
                }
if (other.expire >= t) {
continue;
                }
if (otherId == id) {
continue;
                }
                cand.push_back({other.expire, otherId});
            }

            sort(cand.begin(), cand.end());

for (constauto& [_, otherId] : cand) {
if (used + add <= M) {
break;
                }
                Texture& other = tex[otherId];
                used -= other.usedSize();
                other.minMip = -1;
                other.expire = -1;
                addLog(t, otherId, -1);
            }

if (used + add > M) {
continue;
            }
        }

bool changed = false;
if (cur.minMip == -1) {
            used += cur.suf[needMip];
            cur.minMip = needMip;
            changed = true;
        } elseif (needMip < cur.minMip) {
            used += cur.suf[needMip] - cur.suf[cur.minMip];
            cur.minMip = needMip;
            changed = true;
        }

        cur.expire = t + D;
if (changed) {
            addLog(t, id, cur.minMip);
        }
    }

for (conststring& line : logs) {
cout << line << '\n';
    }
return0;
}
  • >
    Java
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

publicclassMain{
privatestaticclassTexture{
long[] suf;
int minMip = -1;
long expire = -1;

        Texture(long base, int cnt) {
long[] level = newlong[cnt];
            level[0] = base;
for (int i = 1; i < cnt; i++) {
                level[i] = level[i - 1] / 4L;
            }

            suf = newlong[cnt + 1];
for (int i = cnt - 1; i >= 0; i--) {
                suf[i] = suf[i + 1] + level[i];
            }
        }

longusedSize(){
if (minMip == -1) {
return0L;
            }
return suf[minMip];
        }

longextraSize(int needMip){
if (minMip == -1) {
return suf[needMip];
            }
if (needMip < minMip) {
return suf[needMip] - suf[minMip];
            }
return0L;
        }
    }

privatestaticclassPairimplementsComparable<Pair> {
long expire;
int id;

        Pair(long expire, int id) {
this.expire = expire;
this.id = id;
        }

@Override
publicintcompareTo(Pair other){
if (expire != other.expire) {
return Long.compare(expire, other.expire);
            }
return Integer.compare(id, other.id);
        }
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner(System.in);

long M = fs.nextLong();
long D = fs.nextLong();
int N = fs.nextInt();

        Map<Integer, Texture> tex = new HashMap<>();
        StringBuilder ans = new StringBuilder();
long used = 0L;

for (int step = 0; step < N; step++) {
long t = fs.nextLong();
int id = fs.nextInt();

if (id == -1) {
                List<Integer> ids = new ArrayList<>(tex.keySet());
                Collections.sort(ids);

for (int curId : ids) {
                    Texture cur = tex.get(curId);
if (cur.minMip != -1 && cur.expire < t) {
                        used -= cur.usedSize();
                        cur.minMip = -1;
                        cur.expire = -1;
                        ans.append(t).append(' ').append(curId).append(' ')
                           .append(-1).append(' ').append(used).append('\n');
                    }
                }
continue;
            }

int needMip = fs.nextInt();
long base = fs.nextLong();
int cnt = fs.nextInt();

if (!tex.containsKey(id)) {
                tex.put(id, new Texture(base, cnt));
            }
            Texture cur = tex.get(id);
long add = cur.extraSize(needMip);

if (used + add > M) {
                List<Pair> cand = new ArrayList<>();
for (Map.Entry<Integer, Texture> entry : tex.entrySet()) {
int otherId = entry.getKey();
                    Texture other = entry.getValue();
if (other.minMip == -1) {
continue;
                    }
if (other.expire >= t) {
continue;
                    }
if (otherId == id) {
continue;
                    }
                    cand.add(new Pair(other.expire, otherId));
                }

                Collections.sort(cand);
for (Pair p : cand) {
if (used + add <= M) {
break;
                    }
                    Texture other = tex.get(p.id);
                    used -= other.usedSize();
                    other.minMip = -1;
                    other.expire = -1;
                    ans.append(t).append(' ').append(p.id).append(' ')
                       .append(-1).append(' ').append(used).append('\n');
                }

if (used + add > M) {
continue;
                }
            }

boolean changed = false;
if (cur.minMip == -1) {
                used += cur.suf[needMip];
                cur.minMip = needMip;
                changed = true;
            } elseif (needMip < cur.minMip) {
                used += cur.suf[needMip] - cur.suf[cur.minMip];
                cur.minMip = needMip;
                changed = true;
            }

            cur.expire = t + D;
if (changed) {
                ans.append(t).append(' ').append(id).append(' ')
                   .append(cur.minMip).append(' ').append(used).append('\n');
            }
        }

        System.out.print(ans);
    }

privatestaticclassFastScanner{
privatefinal InputStream in;
privatefinalbyte[] buf = newbyte[1 << 16];
privateint ptr = 0;
privateint len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

privateintread()throws Exception {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

longnextLong()throws Exception {
int c;
do {
                c = read();
            } while (c <= 32);

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long val = 0;
while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
return val * sign;
        }

intnextInt()throws Exception {
return (int) nextLong();
        }
    }
}

✨ 写在最后：

网站最近上线了八股和选额的功能啦。

最近卡片刷题已经全员开放了，八股和选择题都能直接刷。 我自己还挺喜欢这种刷法的，先看题、自己想，再翻面看答案，会比一直往下看题库更有“在准备面试”的感觉一点。 如果你最近也在刷八股，准备面试、可以来bishipass试试看哦。

【笔试突围】4月2日网易真题解析+在线刷题 第2张
【笔试突围】4月2日网易真题解析+在线刷题 第3张
【笔试突围】4月2日网易真题解析+在线刷题 第4张
【笔试突围】4月2日网易真题解析+在线刷题 第5张

文章来源： 四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！

上一个天津高考真题几何体串烧

下一个英语是个好同志|逐词逐句读高考真题(2026-04-3)

相关文章

抱歉，评论功能暂时关闭!