CSP-J 历年复赛 T2 及解析（2019~2025）

摘要：本文系统整理了 2019-2025 年 CSP-J 复赛 T2 的历年真题，涵盖公交换乘、直播获奖、插入排序、解密、公路、地图探险、座位等 7 道题目。每道题均提供清晰的思路要点、解题步骤、易错点分析和完整参考代码，帮助选手掌握 T2常考的模拟、贪心、二分、数学等核心算法，提升解题能力。

说明 & 备考建议

题目都可以在洛谷上搜名称就会出来，题目名称也都加了链接点击就能跳转到做题页面。

T2 一般考察基础算法，难度在【普及- ~ 普及/提高- 】之间。 常考算法知识点有：二分、排序、贪心、大模拟，其中简化题意又包含了数学思维推导的考察。 最近两年都是矩阵模拟操作类题目，其实思维难度有降低，但非常考验基本功和细致度。

一些需要注意的点：

Day Day Up！祝大家都能在比赛取得好成绩！✿✿ヽ(°▽°)ノ✿

历年 CSP-J 复赛 T2（2019~2025）

题目列表

题目详解

公交换乘

思路要点

简单来说，小轩要坐

n

n

n 次车，要么是地铁（0），要么是公交（1）。

• 坐地铁：必须花钱，但会赠送一张“优惠券”。这张券有两个限制：① 限时：45 分钟内有效；② 限价：只能用于票价

  ≤

  \\le

  ≤ 这次地铁票价的公交车。

• 坐公交：能用券就优先用券（免单），有多张能用的券时，先用最早获得的。没券可用就只能老老实实花钱。

• 目标：计算坐完

  n

  n

  n 次车后的最低总花费。

这道题的本质是：线性结构（动态数组/队列）的模拟，并利用双指针（滑动窗口）进行时间复杂度的优化。

关键思路

暴力思路的局限性

最直观的想法是：每次遇到公交车，我们就从头到尾扫描一遍之前所有获得过的优惠券，看看哪张没用过、没过期、且价格够。但是，看一下数据范围：

n

≤

10

5

n \\le 10^5

n≤105。如果每次坐公交都全量扫描前面的优惠券，最坏情况下的时间复杂度是

O

(

n

2

)

O(n^2)

O(n2)，总运算量会达到

10

10

10^{10}

1010级别，在竞赛中绝对会 TLE（超时）。

核心优化：双指针/队列思想

如何优化？题目中藏着两个非常关键的“隐藏线索”：

• 时间递增：输入数据是按乘车时间单调递增给出的。

• 45分钟时效：优惠券有效期只有 45 分钟，且同一分钟内不会有两次记录。这意味着在任何一个时间点，还没过期的优惠券最多只有 45 张。

既然过期的券再也不可能被使用了，我们就可以像队列一样，维护一个“有效券池”。每次遇到新记录：

解题步骤

我们以以下样例输入为例，模拟计算机的执行过程：

6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135

本题易错点

• 坑一：忽略换乘价格条件

  要点提醒：免费换乘的条件有两个：一个是时间要不超过 45 分钟，另一个是“公交票价

  ≤

  \\le

  ≤ 地铁票价”，两个都必须满足才能换乘。代码中 tk[j].p 是地铁票，p 是公交票，因此是 tk[j].p >= p。

• 坑二：数据范围与类型

  要点提醒： 总花费 s 最大可能为

  10

  5

  ×

  1000

  =

  10

  8

  10^5 \\times 1000 = 10^8

  105×1000=108，在 int 的表示范围内（约

  2

  ×

  10

  9

  2 \\times 10^9

  2×109）。虽然此题不需要开 long long，但养成每道题评估数据总和、防止溢出的习惯是非常重要的。

• 坑三：不作任何剔除，每次都从 0 遍历到 i

  要点提醒： 这就是前面提到的

  O

  (

  n

  2

  )

  O(n^2)

  O(n2)纯暴力，在

  n

  =

  10

  5

  n = 10^5

  n=105的数据面前会超时。必须学会利用“时间单调递增”这个性质做单向的 head++ 优化。

参考代码-手写队列

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

int n, x, p, t, s; // n:记录数, x:类型, p:票价, t:时间, s:总花费
int head, tail; // 手写队列的头指针和尾指针

struct T{
int p, t; // p:地铁票价, t:获得时间
bool u; // u:是否被用过（默认初始化为 false/0）
}tk[maxn]; // 优惠券队列池

int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d %d %d", &x, &p, &t);
if(!x){ // 如果是地铁（x == 0）
s += p; // 地铁必须雷打不动地花钱
tk[tail++] = {p, t}; // 获得一张优惠券，入队，尾指针后移
}
else{ // 如果是公交车（x == 1）
bool f = 0; // 标记变量，记录当前公交是否成功使用了优惠券
// 核心优化：利用时间单调性，将绝对过期的券从队头永久剔除
while(head < tail && t – tk[head].t > 45){
head++; // 队头后移，相当于出队
}
// 在未过期的有效券池中，从前往后寻找第一张能用的券
for(int j = head; j < tail; j++){
// 找第一张价格 ok 且没用过的换乘票
if(tk[j].p >= p && !tk[j].u){
tk[j].u = 1; // 标记用过
f = 1; // 标记找到
break; // 结束查找
}
}
if(!f){ // 如果遍历完所有有效的券都无法免单
s += p; // 只能自费购买公交票
}
}
}
printf("%d", s); // 输出最终的总花费
return 0;
}

补充解法：使用 STL 容器 – deque

这种解法非常优雅，充分利用了 C++ 标准库的强大功能。

在上一个手写数组的版本中，我们是通过 打标记（tk[j].u = 1） 来表示优惠券被用掉了。而在这个 STL 版本中，思路变得更加直观和暴力：用掉了，就直接把它从队列里“撕掉”（删除）！

可以通过下面这个简单的映射，来看看 STL 是如何简化代码逻辑的：

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

// n: 乘车记录数, x: 交通工具类型(0地铁, 1公交), p: 当次票价, t: 乘车时间, s: 总花费
int n, x, p, t, s;

struct T{ // 定义优惠票的结构体
int p, t; // p: 产生该票时的地铁票价, t: 获得该票的时间
};

int main(){
// 读入乘车记录的总数
scanf("%d", &n);
// 使用双端队列存储手中现有的优惠票
deque<T> tk; // 因为时间是递增的，先获得的票一定在队列头部，方便后续过期清理

for(int i = 1; i <= n; i++){
// 读入当前记录：交通工具类型、票价、时间
scanf("%d %d %d", &x, &p, &t);

if(!x){ // 【情况 0】：乘坐的是地铁
s += p; // 地铁必须自费，累加到总花费中
tk.push_back({p, t}); // 获得一张新的优惠票，放入队列尾部
}
else{ // 【情况 1】：乘坐的是公交车
bool f = 0; // 记录当前公交车是否使用了优惠票（0-没用，1-用了）
// 核心步骤 1：清理过期票
// 因为乘车时间单调递增，已经过期的票直接从队头永久弹出
while(!tk.empty() && t – tk.front().t > 45){
tk.pop_front();
}
// 核心步骤 2：寻找最早可用的优惠票
// 从队头（时间最早）开始向后遍历当前所有未过期的优惠票
for(auto it = tk.begin(); it != tk.end(); ++it){
// 优惠票面额(地铁票价) >= 当前公交车票价，说明满足免费条件
if(it->p >= p){
tk.erase(it); // 消耗掉这张优惠票，从队列中抹去
f = 1; // 标记成功使用优惠票
break; // 找到第一张可用的就立即结束查找
}
}

// 核心步骤 3：未享受优惠的处理（f = 0）
// 如果遍历了所有有效票都没有找到合适的，公交车只能自费
if(!f){
s += p; // 累加公交车票价到总花费
}
}
}

// 输出最终计算出的总花费
printf("%d", s);
return 0;
}

直播获奖

思路要点

这道题目的核心场景是：一场比赛不断有选手的成绩被公布，我们需要在每一次公布新成绩时，实时计算并播报当前的“获奖分数线”。

• 当前参赛总人数：随着成绩公布依次递增（从 1 到

  n

  n

  n）。

• 当前计划获奖人数：公式为

  max

  ⁡

  (

  1

  ,

  ⌊

  当前人数

  ×

  获奖百分比

  ⌋

  )

  \\max(1, \\lfloor \\text{当前人数} \\times \\text{获奖百分比} \\rfloor)

  max(1,⌊当前人数×获奖百分比⌋)。

• 分数线定义：将所有已出成绩从高到低排序，排在“计划获奖人数”名次上的那个分数，就是当前的分数线。

剥去“直播”、“获奖率”的外壳，它本质在考察数据的动态插入与第

K

K

K 大值的快速查询。

关键思路

如果在每次读入新成绩后都用 std::sort 对已有成绩进行排序，时间复杂度将达到

O

(

n

2

log

⁡

n

)

O(n^2 \\log n)

O(n2logn)。结合题目给出的最大数据量

n

=

10

5

n = 10^5

n=105，必定会导致超时（TLE）。

突破口在哪里？

观察数据范围：虽然选手最多有

10

5

10^5

105 人，但每个选手的成绩最高只有 600 分！

当数据的值域（0~600）远远小于数据的个数（

10

5

10^5

105）时，我们应该立刻条件反射般地想到一种以空间换时间的利器：桶排序（计数排序）。

我们可以建立一个大小为 605 的数组 c 作为“桶”，下标表示分数，存储的值表示“获得该分数的总人数”。每次新来一个成绩，只需要用

O

(

1

)

O(1)

O(1) 的时间把它丢进对应的桶里。查询时，从 600 分向 0 分倒序遍历，累加每个桶里的人数，一旦累加人数达到或超过当前的“计划获奖人数”，当前的桶代表的分数就是我们要找的分数线。

解题步骤

我们以局部数据为例，假设

w

=

30

w = 30

w=30，依次读入前

3

3

3 个成绩：100 100 600，模拟代码的执行过程：

本题易错点

• 坑一：暴力排序法

  要点提醒：用一个数组存入前

  i

  i

  i 个数，每读入一个数就调用一遍 sort。时间复杂度高达

  O

  (

  N

  2

  log

  ⁡

  N

  )

  O(N^2 \\log N)

  O(N2logN)，只能拿到前几个

  N

  =

  10

  N=10

  N=10 或

  N

  =

  500

  N=500

  N=500 的部分分测试点。

• 坑二：忽略了同分并列机制

  要点提醒： 题目提到“实际获奖人数可能比计划中多”。桶排序天然解决了这个问题：只要减去当前分数的人数后 t <= 0，就意味着这个分数段的人都能获奖，且刚好包含或超额满足了剩余名额。

• 坑三：桶数组开得太小

  要点提醒： 成绩范围是

  0

  ≤

  score

  ≤

  600

  0 \\le \\text{score} \\le 600

  0≤score≤600，有些同学习惯性写 c[600]，导致存储满分 600 分时数组越界。正确的开法是至少开到 601（代码中开 605 是非常好的竞赛习惯，留有余地）。

参考代码

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

int n, w, x, c[605]; // n为总人数, w为获奖率, x为当前成绩, c为桶数组(成绩最大600)

int main(){
scanf("%d %d", &n, &w);
for(int i = 1; i <= n; i++){
scanf("%d", &x);
c[x]++; // 将新读入的成绩放入对应的桶中，该分数人数+1

// 计算当前计划获奖人数
int t = i * w / 100.0;
t = max(1, t); // 保证至少有1人获奖

// 分配获奖名额：从满分600分开始向低分遍历
for(int j = 600; j >= 0; j—){
if(c[j]){ // 如果有选手考了 j 分
t -= c[j]; // 消耗对应的获奖名额
if(t <= 0){ // 名额分配完毕（或由于同分并列导致超额分配）
printf("%d ", j); // 此时的 j 即为分数线
break; // 找到分数线后立刻跳出内层循环
}
}
}
}
return 0;
}

插入排序

思路要点

这道题目的外壳包装了“插入排序算法”的伪代码，并给出了两种操作。如果直接照着题目去每次做插入排序，就掉进了出题人的陷阱。题目本质其实就是在维护一个数组。

• 操作 1：单点修改，把数组中某一个元素的值改掉。

• 操作 2：单点查询，问如果我们此刻对数组进行一次稳定的升序排序（插入排序的特性），原来在第

  x

  x

  x 个位置的元素，现在排在第几号位置？（注意：查询不会真的改变原数组的顺序）。

考察核心知识点：稳定排序（Stable Sort）的相对位置关系、离线与在线查询、时间复杂度分析。

关键思路

如何快速知道原来在第

x

x

x 个位置的元素，排序后排第几？容易想到每次遇到操作 2，就把数组复制一份，然后用 std::sort 排个序找位置。这种做法每次查询需要

O

(

n

log

⁡

n

)

\\mathcal{O}(n \\log n)

O(nlogn) 的时间，总时间复杂度会直接爆炸，导致超时（TLE）。

破局点在于：计算“排名”（Rank）

要确定一个元素排序后的位置，我们根本不需要把整个数组排好序，**只需要数一数“有多少个元素应该排在它前面”即可。**根据稳定排序的规则：

• 原本在

  x

  x

  x 前面的元素（

  i

  <

  x

  i < x

  i<x）：只有当它们的值严格大于

  a

  x

  a_x

  ax​ 时，才会被挤到

  x

  x

  x 后面去。否则它们依然在

  x

  x

  x 前面。

• 原本在

  x

  x

  x 后面的元素（

  i

  >

  x

  i > x

  i>x）：只有当它们的值严格小于

  a

  x

  a_x

  ax​ 时，才会跑到

  x

  x

  x 前面去。如果它们等于

  a

  x

  a_x

  ax​，因为是“稳定排序”，它们依然要乖乖待在

  x

  x

  x 后面。

因此，我们假设

a

x

a_x

ax​ 的初始排名就是

x

x

x。遍历整个数组：

• 遇到

  i

  <

  x

  i < x

  i<x 且

  a

  i

  >

  a

  x

  a_i > a_x

  ai​>ax​，说明这个元素跑到后面去了，

  x

  x

  x 的排名往前升一位（排名数字减 1）。

• 遇到

  i

  >

  x

  i > x

  i>x 且

  a

  i

  <

  a

  x

  a_i < a_x

  ai​<ax​，说明这个元素跑到前面来了，

  x

  x

  x 的排名往后降一位（排名数字加 1）。

每次查询只需遍历一遍数组，时间复杂度

O

(

n

)

\\mathcal{O}(n)

O(n)。

解题步骤

我们以以下样例输入为例，模拟计算机的执行过程：

3 4
3 2 1
2 3
1 3 2
2 2
2 3

初始数组：n = 3，数组 a = [3, 2, 1]

本题易错点

• 坑一：遇到相同大小的元素（

  a

  i

  =

  a

  x

  a_i = a_x

  ai​=ax​）时的处理规则

  要点提醒：插入排序是稳定排序。所谓稳定，就是指如果两个元素大小一样，原本在前面的，排序后依然在前面。

  • 对于

    i

    <

    x

    i < x

    i<x（原本在前面）：只有

    a

    i

    >

    a

    x

    a_i > a_x

    ai​>ax​ 才会改变相对位置。如果

    a

    i

    =

    a

    x

    a_i = a_x

    ai​=ax​，它依然在

    x

    x

    x 前面，不影响

    x

    x

    x 的排名。所以在第一个循环中，判断条件必须是严格大于 (>)，绝不能写成 >=。

  • 对于

    i

    >

    x

    i > x

    i>x（原本在后面）：只有

    a

    i

    <

    a

    x

    a_i < a_x

    ai​<ax​ 才会越过

    x

    x

    x 跑到前面。如果

    a

    i

    =

    a

    x

    a_i = a_x

    ai​=ax​，它依然要在

    x

    x

    x 后面，不影响

    x

    x

    x 的排名。所以在第二个循环中，判断条件必须是严格小于 (<)，绝不能写成 <=。

• 坑二：使用 sort() 排序

  要点提醒： 如果每次查询都排序，单次查询复杂度为

  O

  (

  n

  log

  ⁡

  n

  )

  \\mathcal{O}(n \\log n)

  O(nlogn)。 最坏情况下，有 200,000 次查询，总运算量大约为

  200000

  ×

  8000

  ×

  log

  ⁡

  2

  (

  8000

  )

  ≈

  2

  ×

  10

  9

  200000 \\times 8000 \\times \\log_2(8000) \\approx 2 \\times 10^9

  200000×8000×log2​(8000)≈2×109 次运算，这在正规比赛 1 秒的时间限制内绝对会超时（TLE）。

参考代码

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

int n, q, op, x, v, a[maxn];

int main(){
scanf("%d %d", &n, &q); // 读入元素个数 n 和操作次数 q
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]); // 循环读入初始数组
}
while(q—){
scanf("%d %d", &op, &x); // 循环处理 $Q$ 次操作，读入操作类型和目标下标
if(op == 1){
scanf("%d", &v); // 若为操作 1，读入修改后的新值 $v$
a[x] = v; // $O(1)$ 完成单点修改
}
else{
int p = x; // 假设排位就是 x
for(int i = 1; i < x; i++){
if(a[i] > a[x]) p—; // 稳定排序核心：原先在前面且严格大于 a[x] 的元素会排到它后面，故 a[x] 排名升 1（数字减 1）
}
for(int i = x + 1; i <= n; i++){
if(a[i] < a[x]) p++; // 稳定排序核心：原先在后面且严格小于 a[x] 的元素会排到它前面，故 a[x] 排名降 1（数字加 1）
}
printf("%d\\n", p); // 打印计算出来的真实排位
}
}
return 0;
}

解密

思路要点

题目一共给出了

k

k

k组询问。每组询问包含三个正整数

n

,

d

,

e

n, d, e

n,d,e，要求我们找出两个正整数

p

p

p和

q

q

q（满足

p

≤

q

p \\le q

p≤q），使得它们同时满足以下两个方程：

• n

  =

  p

  ×

  q

  n = p \\times q

  n=p×q

• e

  ×

  d

  =

  (

  p

  −

  1

  )

  (

  q

  −

  1

  )

  +

  1

  e \\times d = (p – 1)(q – 1) + 1

  e×d=(p−1)(q−1)+1

如果能找到这样的

p

p

p和

q

q

q，就输出它们；如果找不到满足条件的正整数，则输出 NO。

本题表面上是一个复杂的“加密/解密”故事，剥去这层外壳后，它的算法本质是：求解二元方程组 / 一元二次方程的整数解。这是一个典型的数学推导题，考察的是同学们将代数式变形并转化为编程逻辑的能力。

关键思路

如果我们尝试去暴力枚举

p

p

p（从

1

1

1 到

n

\\sqrt{n}

n

​），由于

n

≤

10

18

n \\le 10^{18}

n≤1018，

n

\\sqrt{n}

n

​ 最大可达

10

9

10^9

109，再加上

k

=

10

5

k = 10^5

k=105 次询问，总运算量会达到惊人的

10

14

10^{14}

1014 级别，绝对会超时（TLE）。

因此，我们必须对已知的方程进行数学化简：

这时候你会惊奇地发现，题目提示中的

m

=

n

−

e

×

d

+

2

m = n – e \\times d + 2

m=n−e×d+2 其实就是

p

+

q

p + q

p+q 的值！

现在，问题转化为了一个经典的数学模型——已知两数之积与两数之和，求这两个数：

• p

  ×

  q

  =

  n

  p \\times q = n

  p×q=n

• p

  +

  q

  =

  m

  p + q = m

  p+q=m

根据韦达定理，

p

p

p 和

q

q

q 恰好是一元二次方程

x

2

−

m

x

+

n

=

0

x^2 – mx + n = 0

x2−mx+n=0 的两个根！根据求根公式，解得：

x

=

m

±

m

2

−

4

n

2

x = \\frac{m \\pm \\sqrt{m^2 – 4n}}{2}

x=2m±m2−4n

​​

因为题目要求

p

≤

q

p \\le q

p≤q，所以我们让

p

p

p 取减号，

q

q

q 取加号：

• p

  =

  m

  −

  m

  2

  −

  4

  n

  2

  p = \\frac{m – \\sqrt{m^2 – 4n}}{2}

  p=2m−m2−4n

  ​​

• q

  =

  m

  +

  m

  2

  −

  4

  n

  2

  q = \\frac{m + \\sqrt{m^2 – 4n}}{2}

  q=2m+m2−4n

  ​​

我们只需要在程序中判断判别式

Δ

=

m

2

−

4

n

\\Delta = m^2 – 4n

Δ=m2−4n 是否大于 0 并且为完全平方数，以及分子是否能被 2 整除即可。

解题步骤

我们以样例输入中的第一组数据 770 77 5 为例，模拟代码的执行过程：

本题易错点

• 坑一：数据范围溢出

  要点提醒：看清数据范围：

  n

  ≤

  10

  18

  n \\le 10^{18}

  n≤1018，

  e

  ×

  d

  ≤

  10

  18

  e \\times d \\le 10^{18}

  e×d≤1018。这意味如果用普通的 int 都会直接爆掉。代码全线要使用 ll（long long），并且中间计算 m * m 和 4 * n 时也用 ll 承接，才能完美避开这个大坑。

• 坑二：漏掉整除判断

  要点提醒： 求根公式中有一个“除以 2”的操作。如果

  m

  −

  r

  m – r

  m−r是个奇数，除以 2 就会产生小数（在计算机整数除法中会向下取整导致答案错误），这就不能满足题目要求的“正整数”了。代码里的 (m – r) % 2 成功拦截了这种情况。

• 坑三：暴力循环枚举

  要点提醒： 妄图通过 for(ll p=1; p*p<=n; p++) 来找答案。测试点 7~10 的

  n

  n

  n都在

  10

  18

  10^{18}

  1018级别，直接卡死卡到 0 分。

参考代码 – 二次方程构造法

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

int k;
ll n, e, d, p, q;
int main(){
scanf("%d", &k); // 读入总询问次数
while(k—){
scanf("%lld %lld %lld", &n, &d, &e); // 严格按照题目顺序读入 n, d, e
ll m = n – e * d + 2; // 数学推导变形，m 核心代表 p + q 的值
// (x – p) * (x – q) = x^2 – (p + q) * x + p * q
ll dt = m * m – 4 * n, r = 0; // dt 为一元二次方程判别式 b^2 – 4ac
if(dt >= 0) r = sqrt(dt); // 当判别式大于等于0时，计算其平方根
// 核心拦截：无实根、非完全平方数、分子不能整除2
if(dt < 0 || r * r != dt || (m – r) % 2){
printf("NO\\n"); // 只要有一项不满足，即为无整数解
continue; // 跳过本次循环，继续下一次询问
}
p = (m – r) / 2; // 依据公式计算出较小的正整数根 p
q = m – p; // 依据和的定义计算出较大的正整数根 q
printf("%lld %lld\\n", p, q); // 格式化输出 p 和 q，保证了 p <= q
}
return 0;
}

参考代码 – 二分法

经过前面的数学推导，我们已经成功把原方程组化简为了经典的“知和知积”模型：

p

+

q

=

m

p + q = m

p+q=m，

p

×

q

=

n

p \\times q = n

p×q=n。

此时，我们可以把

q

q

q 用

m

−

p

m – p

m−p 代替，消去变量

q

q

q，得到关于

p

p

p 的一元方程：

p

×

(

m

−

p

)

=

n

p \\times (m – p) = n

p×(m−p)=n。

由于题目设定

p

≤

q

p \\le q

p≤q，当

p

p

p 和

q

q

q 无限接近时，

p

p

p 最大只能取到

m

2

\\frac{m}{2}

2m​。因此，

p

p

p 的合法取值范围被严格锁定在整数区间

[

1

,

m

2

]

[1, \\frac{m}{2}]

[1,2m​]。

我们设一个关于

p

p

p 的函数：

f

(

p

)

=

p

×

(

m

−

p

)

f(p) = p \\times (m – p)

f(p)=p×(m−p)

在线性代数或二次函数图像中，当

p

∈

[

1

,

m

2

]

p \\in [1, \\frac{m}{2}]

p∈[1,2m​] 时，随着

p

p

p 的增大，

f

(

p

)

f(p)

f(p) 的值是严格单调递增的。

• 如果我们猜的

  p

  p

  p 偏小，计算出来的乘积

  p

  ×

  q

  p \\times q

  p×q 就会小于

  n

  n

  n；

• 如果我们猜的

  p

  p

  p 偏大，计算出来的乘积

  p

  ×

  q

  p \\times q

  p×q 就会大于

  n

  n

  n。

既然区间固定，且函数值具备严格的单调性，这便是天造地设的“二分答案”场景！ 我们可以直接在

[

1

,

m

2

]

[1, \\frac{m}{2}]

[1,2m​] 区间内二分枚举

p

p

p 的值。

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

int k;
ll n, e, d, p, q;
int main(){
scanf("%d", &k); // 读入总询问次数
while(k—){
bool f = 0; // 核心标记：初始化为 0 表示当前这组询问尚未找到解
scanf("%lld %lld %lld", &n, &d, &e); // 按照题目顺序读入 n, d, e
ll m = n – e * d + 2; // 数学推导变形，m 代表 p + q 的值
ll l = 1, r = m / 2; // 根据 p <= q 锁定 p 的上下界，建立二分闭区间 [l, r]
while(l <= r){
ll mid = (l + r) >> 1; // mid 二分枚举 p 的可能取值
ll q = m – mid; // 联动计算出对应的 q 值
if(mid * q < n){
l = mid + 1; // 实际乘积偏小，说明 mid 猜小了，左边界右移
}
else if(mid * q > n){
r = mid – 1; // 实际乘积偏大，说明 mid 猜大了，右边界左移
}
else{
printf("%lld %lld\\n", mid, q); // 乘积完美相等，找到正整数解并打印
f = 1; // 将标记置为 1，代表有解
break; // 提前结束二分查找，节省效率
}
}
if(!f){
printf("NO\\n"); // 如果二分区间找满仍未触发 else，说明无整数解，输出 NO
}
}

return 0;
}

公路

思路要点

想象一下你正在进行一场自驾游，从

1

1

1 号点开到

n

n

n 号点。每个站点之间的距离不同，而且每个站点的油价也高低不一。 你的油箱是无限大的，但你每到一个新站点，都只能买整数升的油。车子每升油能跑

d

d

d 公里。

我们的目标是：妥善安排在哪些站点加多少油，使得安全到达终点

n

n

n 时的总花费最少。本题表面上是一个复杂的自驾游模拟，剥去它的“外壳”，其本质是一个贪心算法（Greedy），配合前缀最小值的维护。

关键思路

• 买油的“反悔”思维：既然油箱无限大，我们在前进的过程中，如果发现当前的站点的油价比之前经过的所有站点都贵，那我们其实应该在“之前最便宜的那个站”就把油加够。

• 前缀最小值维护：我们只需要在从左到右遍历站点时，顺便记录一下“到目前为止，我见过的最便宜的油价是多少”。每当需要为下一段路程买油时，都按这个历史最便宜的价格来算账。

• 余量管理：因为只能买整数升的油，所以每次加完油往往会“跑超”一点点。这个超出的里程（里程余量）可以留给下一段路使用，必须精准扣除。

凡是题目中出现“资源可以无限囤积，沿途代价不断变化，要求单向移动的总代价最小”的路线规划题，基本都可以锁定为“历史最低价加油”的贪心模型。

解题步骤

我们以样例输入

n

=

5

,

d

=

4

n = 5, d = 4

n=5,d=4，路程

v

=

[

10

,

10

,

10

,

10

]

v = [10, 10, 10, 10]

v=[10,10,10,10]，油价

a

=

[

9

,

8

,

9

,

6

,

5

]

a = [9, 8, 9, 6, 5]

a=[9,8,9,6,5] 为例，手演一遍程序的执行过程。

在这个过程中，我们初始化总花费 s = 0，历史最低油价 mina = INT_MAX，历史最低油价站点 p = 1，以及之前的里程余量 r = 0。

• 第 1 站 (

  i

  =

  1

  i = 1

  i=1)：读入当前站油价 a[1] = 9。

  • 更新历史最低价：由于

    9

    <

    INT_MAX

    9 < \\text{INT\\_MAX}

    9<INT_MAX，所以 mina 变成

    9

    9

    9，最便宜站点指针 p = 1。

  • 计算当前段所需里程：下一段路长 v[1] = 10，减去之前的余量 r = 0，实际还需要跑

    10

    10

    10 公里。

  • 计算加油量：用 ceil(1.0 * 10 / 4) 向上取整得到 t = 3 升。

  • 算账：在第 p 站（即第 1 站）买

    3

    3

    3 升油，花费 s += 3 * 9，此时总花费 s = 27。

  • 更新余量：

    3

    3

    3 升油能跑

    12

    12

    12 公里，实际只跑了

    10

    10

    10 公里，剩下 r = 2 公里留给下一站。

• 第 2 站 (

  i

  =

  2

  i = 2

  i=2)：读入当前站油价 a[2] = 8。

  • 更新历史最低价：由于

    8

    <

    9

    8 < 9

    8<9，发现更便宜的站了！更新 mina = 8，p = 2。

  • 计算当前段所需里程：下一段路长 v[2] = 10，减去上一站留下的余量 r = 2，实际还需要跑

    8

    8

    8 公里。

  • 计算加油量：用 ceil(1.0 * 8 / 4) 刚好整除，得到 t = 2 升。

  • 算账：在当前最便宜的第 p 站（即第 2 站）买

    2

    2

    2 升油，花费 s += 2 * 8，此时总花费 s = 27 + 16 = 43。

  • 更新余量：

    2

    2

    2 升油跑

    8

    8

    8 公里，刚好把路跑完，余量 r = 0。

• 第 3 站 (

  i

  =

  3

  i = 3

  i=3)：读入当前站油价 a[3] = 9。

  • 更新历史最低价：由于

    9

    >

    8

    9 > 8

    9>8，不更新。当前最便宜的油价依然是 mina = 8，对应的站点依然是 p = 2。

  • 计算当前段所需里程：下一段路长 v[3] = 10，减去余量 r = 0，实际还需要跑

    10

    10

    10 公里。

  • 计算加油量：用 ceil(1.0 * 10 / 4) 向上取整得到 t = 3 升。

  • 算账：虽然现在在第 3 站，但我们可以假装在第 p 站（第 2 站）多买了

    3

    3

    3 升油！花费 s += 3 * 8，此时总花费 s = 43 + 24 = 67。

  • 更新余量：

    3

    3

    3 升油跑

    12

    12

    12 公里，减去路程

    10

    10

    10，留下余量 r = 2 公里。

• 第 4 站 (

  i

  =

  4

  i = 4

  i=4)：读入当前站油价 a[4] = 6。

  • 更新历史最低价：由于

    6

    <

    8

    6 < 8

    6<8，又找到了更便宜的站！更新 mina = 6，p = 4。

  • 计算当前段所需里程：下一段路长 v[4] = 10，减去余量 r = 2，实际还需要跑

    8

    8

    8 公里。

  • 计算加油量：用 ceil(1.0 * 8 / 4) 得到 t = 2 升。

  • 算账：在最便宜的第 p 站（第 4 站）买

    2

    2

    2 升油，花费 s += 2 * 6，此时总花费 s = 67 + 12 = 79。

  • 更新余量：余量 r = 0。

• 第 5 站 (

  i

  =

  5

  i = 5

  i=5)：

  • 读入当前站油价 a[5] = 5。

  • 因为已经到达终点（i == n），触发 continue，结束循环。

  • 最终输出结果：s = 79。

本题易错点

• 坑一：数据范围爆 int

  要点提醒：是本题最大的陷阱。看数据范围，总路程可以达到

  10

  5

  ×

  10

  5

  =

  10

  10

  10^5 \\times 10^5 = 10^{10}

  105×105=1010 公里。如果油价也是

  10

  5

  10^5

  105，总花费最大可能达到

  10

  15

  10^{15}

  1015 左右，远远超出了 int 的最大值（约

  2

  ×

  10

  9

  2 \\times 10^9

  2×109）。因此，总花费 s 必须开 long long，且在计算 t * a[p] 时，必须引入 1LL 强制进行类型提升。

• 坑二：局部贪心（走一步看一步）

  要点提醒： 有同学误以为到了

  i

  i

  i 站，就只买刚刚好走到

  i

  +

  1

  i+1

  i+1 站的油。这会导致如果

  i

  i

  i 站很便宜，而

  i

  +

  1

  i+1

  i+1 站很贵，车主却无法在

  i

  i

  i 站多买点油囤着，从而浪费了省钱的机会。

参考代码

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

int n, d, v[maxn], a[maxn];
long long s; // 终点总花费，用 long long 防止爆 int

int main(){
// 读入站点数和每升油可前进距离
scanf("%d %d", &n, &d);
for(int i = 1; i < n; i++){
scanf("%d", &v[i]);
}

int mina = INT_MAX, p = 1, r = 0; // mina:历史最低油价, p:最低油价站点, r:之前的里程余量

for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
if(i == n) continue; // 到达终点，不需要在终点加油

// 贪心策略：维护到达当前位置为止的最低油价和站点
if(a[i] < mina){
mina = a[i];
p = i;
}

// 计算在当前历史最便宜站点 p 应该购买的油量 t
int t = ceil(1.0 * (v[i] – r) / d);
s += 1LL * t * a[p]; // 1LL 防止 t * a[p] 计算时爆 int
r += (t * d – v[i]); // 更新走完这一段后，多出来的里程余量
}

printf("%lld", s);

return 0;
}

地图探险

思路要点

题目给我们一个

n

×

m

n \\times m

n×m的格子地图，里面有两种格子：. 代表可以通过的空地，x 代表无法通过的障碍物。

机器人有一个初始位置

(

x

0

,

y

0

)

(x_0, y_0)

(x0​,y0​)和一个初始朝向

d

0

d_0

d0​（0东、1南、2西、3北）。它一共要连续做

k

k

k步操作。每一步的行动规则很简单：

• 试探着往当前方向向前走一步。

• 如果前方在地图内且是空地，它就开心地走过去，方向不变。

• 如果前方超出了地图边界或者踩到了障碍物，它就不动，原地向右转 90 度（顺时针转弯）。

我们要做的，就是帮它数一数：在走完

k

k

k步之后，地图上有多少个不同的格子被它踩过（注意：起点也算踩过，重复踩到的格子只能算一次）。

这是一道非常典型的二维网格图状态模拟题。它本质上考查的是 “数组边界控制” 与 “方向数组（常数偏移量）” 的联合运用。题目没有任何复杂的算法（如不需要深搜 DFS 或广搜 BFS），只要完全按照题目给定的规则，用代码一步步模拟机器人的移动即可。

关键思路

由于机器人的下一步行动是由当前状态唯一确定的，它没有“分支选择”，因此直接进行顺序模拟是最高效、最稳妥的方法。我们如何将复杂的方向转化和格子移动优雅地写成代码呢？

• 方向数组的妙用：

处理二维网格移动时，千万不要写一堆 if (d == 0) y++; else if (d == 1) x++; 这样的冗长代码。我们可以定义一个二维数组来表示方向的变化量（偏移量）：int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};这样，当方向为 p 时，下一步的坐标就是 x + d[p][0] 和 y + d[p][1]。

• 顺时针旋转的数学表达：

题目中说向右转，对应的数字变化是：0

→

\\rightarrow

→ 1

→

\\rightarrow

→ 2

→

\\rightarrow

→ 3

→

\\rightarrow

→ 0。

这在数学上可以用取模运算（%）完美解决：

p

=

(

p

+

1

)
 

m

o

d

4

p = (p + 1) \\bmod 4

p=(p+1)mod4。

• **数据范围与时空复杂度：**对于所有数据，

  T

  ≤

  5

  T \\le 5

  T≤5，

  n

  ,

  m

  ≤

  10

  3

  n, m \\le 10^3

  n,m≤103，

  k

  ≤

  10

  6

  k \\le 10^6

  k≤106。

  • 时间复杂度：每一组数据我们只需要循环模拟

    k

    k

    k次，每次移动的操作都是

    O

    (

    1

    )

    O(1)

    O(1)的。因此总时间复杂度为

    O

    (

    T

    ×

    k

    )

    O(T \\times k)

    O(T×k)，最大计算量在

    5

    ×

    10

    6

    5 \\times 10^6

    5×106左右。在计算机 1 秒可以运行约

    10

    8

    10^8

    108次运算的背景下，这个纯模拟解法可以轻松 AC。

  • 空间复杂度：由于地图最大为

    1000

    ×

    1000

    1000 \\times 1000

    1000×1000，开辟两个 1005 × 1005 的 bool 数组只需要约 2MB 内存，远低于比赛限制。