京东笔试 京东笔试题 0816
笔试时间：2025年8月16日
往年笔试合集：
第一题
你有一个长度为n的序列A: a₁,a₂,…,aₙ，你需要进行如下操作至多一次: 选择一个区间[L,R] (1≤L≤R≤n)，将a_L,a_{L+1},…,a_R全部加1。即a_L,a_{L+1},…,a_R均变为a_L+1,a_{L+1}+1,…,a_R+1 设变化后的序列为B: b₁,b₂,…,bₙ，你需要最大化inv(A)-inv(B)，其中inv()函数表示该序列的逆序对数量，即满足i<j，a_i>a_j的二元组(i,j)个数。换句话说，你需要尽可能地减小序列A的逆序对数量。
输入描述
第一行一个正整数T，表示数据组数; 对于每一组数据，第一行一个正整数n;
第二行n个正整数a₁,a₂,…,aₙ，表示序列A。 1≤n≤10⁵; 1≤T≤5; 1≤a_i≤n。
输出描述
对于每一组数据，输出一个整数，表示最大的inv(A)-inv(B)。
样例输入
3
5
4 2 3 1 5
5
1 2 3 4 5
3
2 1 1
样例输出
2
0
2
说明： 第一组数据，选择区间[3,4]，变化后的序列为[4 2 4 2 5]，逆序对数量为3;变化前逆序对数量为5。 第二组数据，选择任意区间都不会减小逆序对数量。 第三组数据，选择区间[2,3]，变化后的序列为[2 2 2]，逆序对数量为0;变化前逆序对数量为2。
参考题解
我们只在一个连续区间把所有数都加 1。对位置 i 的值 v 来说，这个操作只影响两种配对： (1) 右边等于 v−1 的元素会让原本的逆序对消失（赚到的收益 = 右侧 v−1 的个数）； (2) 左边等于 v+1 的元素会新产生逆序对（损失 = 左侧 v+1 的个数）。 所以位置 i 的净收益 = 右侧(v−1)数量 − 左侧(v+1)数量。预处理每个取值的全局出现次数 totalCount[·]，边扫边维护左侧计数 seenPrefix[·]，就能在 O(1) 得到当前位置的增量，把这些增量累加得到把区间一直向右扩的总收益，遍历过程中取到的最大值就是答案。时间复杂度 O(n)，空间 O(n)。
C++：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) cin >> arr[i];
vector<int> totalCount(n + 2, 0);
for (int v : arr) ++totalCount[v];
vector<int> seenPrefix(n + 3, 0);
long long currentGain = 0;
long long bestGain = 0;
for (int i = 0; i < n; ++i) {
bestGain = max(bestGain, currentGain);
int v = arr[i];
currentGain += (long long)totalCount[v - 1] - seenPrefix[v - 1] - seenPrefix[v + 1];
++seenPrefix[v];
}
bestGain = max(bestGain, currentGain);
cout << bestGain << "\n";
}
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class Main {
// 快速读入
private static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, x = 0;
do { c = read(); } while (c <= 32 && c != -1);
if (c == '-') { sgn = -1; c = read(); }
while (c > 32 && c != -1) {
x = x * 10 + (c - '0');
c = read();
}
return x * sgn;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
StringBuilder out = new StringBuilder();
int T;
try { T = fs.nextInt(); } catch (Exception e) { return; }
for (int _t = 0; _t < T; _t++) {
int n = fs.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = fs.nextInt();
int[] totalCount = new int[n + 2];
for (int v : arr) ++totalCount[v];
int[] seenPrefix = new int[n + 3];
long currentGain = 0L;
long bestGain = 0L;
for (int i = 0; i < n; i++) {
if (currentGain > bestGain) bestGain = currentGain;
int v = arr[i];
currentGain += (long) totalCount[v - 1] - seenPrefix[v - 1] - seenPrefix[v + 1];
++seenPrefix[v];
}
if (currentGain > bestGain) bestGain = currentGain;
out.append(bestGain).append('\n');
}
System.out.print(out.toString());
}
}
Python：
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
try:
T = next(it)
except StopIteration:
return
out_lines = []
for _ in range(T):
n = next(it)
arr = [next(it) for _ in range(n)]
total = [0] * (n + 2)
for v in arr:
total[v] += 1
seen = [0] * (n + 3)
current = 0
best = 0
for v in arr:
if current > best:
best = current
current += total[v - 1] - seen[v - 1] - seen[v + 1]
seen[v] += 1
if current > best:
best = current
out_lines.append(str(best))
sys.stdout.write("\n".join(out_lines))
if __name__ == "__main__":
main()
第二题
在一场跳水比赛中，共有n位裁判依次为选手打分（打分为非负整数）。根据比赛规则，需要从所有裁判的打分中，选取连续的m个打分来计算选手的
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
