网硕互联帮助中心欢迎大家订阅我的专栏：算法题解：C++与Python实现！ 本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色 1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。 2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年黄金组真题解析 | 汇总
P2880 Balanced Lineup
【题目来源】
洛谷：[P2880 USACO07JAN] Balanced Lineup G – 洛谷
【题目描述】
每天，农夫 John 的
n
(
1
≤
n
≤
5
×
10
4
)
n\\ (1\\le n\\le 5\\times 10^4)
n (1≤n≤5×104) 头牛总是按同一序列排队。
有一天，John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了
q
(
1
≤
q
≤
1.8
×
10
5
)
q\\ (1\\le q\\le 1.8\\times10^5)
q (1≤q≤1.8×105) 个可能的牛的选择和所有牛的身高
h
i
(
1
≤
h
i
≤
10
6
,
1
≤
i
≤
n
)
h_i\\ (1\\le h_i\\le 10^6,1\\le i\\le n)
hi (1≤hi≤106,1≤i≤n)。他想知道每一组里面最高和最低的牛的身高差。
【输入】
第一行两个数
n
,
q
n,q
n,q。
接下来
n
n
n 行，每行一个数
h
i
h_i
hi。
再接下来
q
q
q 行，每行两个整数
a
a
a 和
b
b
b，表示询问第
a
a
a 头牛到第
b
b
b 头牛里的最高和最低的牛的身高差。
【输出】
输出共
q
q
q 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。
【输入样例】
6 3
1
7
3
4
2
5
1 5
4 6
2 2
【输出样例】
6
3
0
【算法标签】
《洛谷 P2880 Balanced Lineup》 #线段树# #树状数组# #ST表# #USACO# #2007#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
// 定义常量
const int N = 50005; // 最大数据量
// 定义数组
int a[N][20]; // ST表，用于存储区间最大值，a[i][j]表示从i开始长度为2^j的区间最大值
int b[N][20]; // ST表，用于存储区间最小值，b[i][j]表示从i开始长度为2^j的区间最小值
int n; // 数据个数
int q; // 查询次数
int maxn; // 临时变量，存储区间最大值
int minn; // 临时变量，存储区间最小值
int main()
{
// 读入数据个数和查询次数
cin >> n >> q;
// 读入初始数据并初始化ST表的第一层
for (int i = 1; i <= n; i++)
{
cin >> a[i][0]; // 输入第i个数
b[i][0] = a[i][0]; // 同时赋值给最小值表
}
// 构建ST表
for (int j = 1; j <= 20; j++) // j表示区间长度为2^j
{
for (int i = 1; i + (1 << j) – 1 <= n; i++) // 确保区间不越界
{
// 计算区间[i, i+2^j-1]的最大值
// 拆分为两个区间：[i, i+2^(j-1)-1] 和 [i+2^(j-1), i+2^j-1]
a[i][j] = max(a[i][j – 1], a[i + (1 << (j – 1))][j – 1]);
// 计算区间[i, i+2^j-1]的最小值
b[i][j] = min(b[i][j – 1], b[i + (1 << (j–1))][j – 1]);
}
}
// 处理查询
while (q—)
{
int l, r; // 查询区间[l, r]
cin >> l >> r;
// 计算区间长度的对数向下取整
int k = log2(r – l + 1);
// 查询区间最大值
// 将区间[l, r]拆分为两个有重叠的区间：
// [l, l+2^k-1] 和 [r-2^k+1, r]
maxn = max(a[l][k], a[r – (1 << k) + 1][k]);
// 查询区间最小值
minn = min(b[l][k], b[r – (1 << k) + 1][k]);
// 输出区间极差（最大值减最小值）
cout << maxn – minn << endl;
}
return 0;
}
【运行结果】
6 3
1
7
3
4
2
5
1 5
6
4 6
3
2 2
0
评论前必须登录！
注册