求区间最大值+求最短满足条件的区间的总结
用到的算法有：
- 二分
- 前缀和
- 双指针
- 单调队列
- RMQ
- 线段树
1 题目
链接： https://ac.nowcoder.com/acm/contest/11229/D
来源：牛客网牛牛参加了牛妹的派对。
牛牛面前有一个圆桌，圆桌边缘按顺序摆上了 n 个蛋糕（第一个蛋糕和第 n 个蛋糕相邻）。
每个蛋糕都有一个饱腹值和奶油含量。
牛牛不喜欢吃奶油，所以他想要在保证自己能吃饱（所吃蛋糕的饱腹度的和大于等于 s）的情况下，所选择的蛋糕中奶油含量最大的那一个的奶油含量越低越好。我们知道，牛牛一直都是个绅士。所以他选择的蛋糕应该是相邻的（也就是对应圆上的一段弧（也可以是整个圆））。
现在它想请你帮它计算在能够吃饱的情况下，他吃到蛋糕中奶油含量最高的那一个最低会是多少？
示例1
输入:
5 9
4 3 7 6 1
1 3 9 2 5
输出:
5
说明
选择第 1，2，4，5 个蛋糕：
饱腹值：4+3+6+1=14>9
最大奶油含量：max{1,3,2,5}=5
所以输出 5。2 思路
首先我们思考一下条件：
- 需要从n个蛋糕中取一段子区间（不是子序列，子区间要求连续）
- 桌子是圆的，在给定的顺序上，同时满足 1 和 n 也是相邻的，所以是从圆里面取一段
- 这一段子区间里蛋糕的饱腹度的和要大于等于 s
- 满足条件3的同时还要满足区间中的蛋糕中奶油含量最大的那一个的奶油含量最低
所以我们从这些条件中构建出模型：
- 求满足饱和度的和大于等于s的区间
- 为了使区间中最大奶油含量最小所以要找到满足田间1的区间并且区间要尽可能短，因为在满足区间和的同时，多一个可能会使最大奶油含量变大，所以尽可能的不加多余的蛋糕
- 求子区间中最大的奶油含量值
我们来一个一个解决：
首先桌子是圆的怎么将n和1 头和尾相连成一个区间？
我们只需将n个蛋糕复制一份放到n的后面就行了，这样头和尾就能相连了。
如图：
接下来我们解决求区间最大值+求最短满足条件的区间的问题
思路1
==二分(nlogn)==
我们可以发现我要们求的是最大的奶油含量值最小，所以我们想能不能用二分来解决
二分的关键点是：
- 找到一个区间使得key在此区间内
- 使得这个区间具有二段性：
- 这两段中有且仅有一段存在key
- key即为其中一段的边界值
我们先看是否有二段性：假设这个key是最终答案，那么比key大的值能不能满足，答案是一定的，因为奶油量越大，所能满足的满足饱和度的和大于等于s的区间越多，所以大于key的值一定能满足，那么比key小的值能不能满足，答案是不能，因为key越小，所能满足条件的区间就越少，key已经是最优答案，所以满足二段性。
我们也可以这样想：把所有子区间找出来并且按最大奶油量的值来排序，你就会发现比最优解小的都不能满足饱和度的和大于等于s，所以可以用二分来写
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
int n, s;
int a[N], b[N];
int ans = 1e9 + 7;
bool check(int x)
{
int sum = 0;
for (int i = 1; i <= 2 * n; i++)
{
if (b[i] <= x)
sum += a[i];
else
sum = 0;
if (sum >= s)
return true;
}
return false;
}
signed main()
{
cin >> n >> s;
ll sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i + n] = a[i];
sum += a[i];
}
if (sum < s)
{
cout << -1;
return 0;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
b[i + n] = b[i];
}
int l = 1, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
cout << r;
return 0;
}思路二 ：求最短满足条件的区间和求区间最大值分开求
求最短满足条件的区间
- 双指针
我们要求一段区间和大于等于s且区间长度最短，可以用双指针来求所有满足条件的子区间
看能不能用双指针算法就看是否具有单调性，当右指针向右走的时候，左指针是否随着右指针移动而向右移动，我们要求区间和并且长度最短，显然满足这个性质，当右指针向右移动时区间和变大，当区间和大于等于s时，就可以让左指针向右移动，为了能让区间长度最短
i sum = 0;
int l = 1;
for (int i = 1; i <= 2 * n; i++)
{
sum += a[i];
while (sum - a[l] >= s)
{
sum -= a[l];
l++;
}
if (sum >= s)
ans = min(ans, query());
}- 二分+前缀和
我们是要找区间和大于等于s的区间并且区间长度最短，那么我们可以用前缀和来快速查找一个区间的和，我们枚举左端点，怎么样能快速找到满足条件的右端点呢，答案是二分,因为饱腹值数组里面的值都是正数，所以它的前缀和数组呈单调递增趋势，所以要想在前缀和数组里找到一个值用二分是没有问题的。
for (int i = 1; i <= 2 * n; i++) // 求前缀和
c[i] = c[i - 1] + a[i];
for (int i = 1; i <= n; i++) //枚举每一个左端点
{
int l = i, r = 2 * n;
while (l < r)
{
int mid = l + r >> 1;
if (c[mid] - c[i - 1] >= s)
r = mid;
else
l = mid + 1;
}
if (c[r] - c[i - 1] >= s)
{
ans = min(ans, query());
}
}求区间最大值
- RMQ（静态查询，值不可更改）
关于RMQ的算法讲解大家可以看这篇文章RMQ 算法（图示）
void init()
{
for (int j = 0; j < M; j++)
{
for (int i = 1; i + (1 << j) - 1 <= n; i++)
{
if (!j)
f[i][j] = b[i];
else
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}- 线段树（动态查询，值可修改）
求一个区间中某个数得最大值，有多种方式，我们可以使用线段树来解决，线段树是一种高级数据结构，用处就是快速查找区间值(最大值、最小值，区间和等等)
struct node
{
int l, r;
int mmax;
} tr[N * 4];
void pushup(int u)
{
tr[u].mmax = max(tr[u << 1].mmax, tr[u << 1 | 1].mmax);
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].mmax;
int mid = (tr[u].l + tr[u].r) >> 1;
int ans = 0;
if (l <= mid)
ans = query(u << 1, l, r);
if (r > mid)
ans = max(ans, query(u << 1 | 1, l, r));
return ans;
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r)
{
tr[u].mmax = b[l];
}
else
{
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}思路3 求最短满足条件的区间的同时求区间最大值
==双指针+单调队列O(n)==
双指针的思路我们上面已经讲过了，用来求满足条件的子区间，我们还要求的是区间的最大值，我们我可以想一下滑动窗口那道题与这道题的区别，滑动窗口是求固定长度区间的最大值，而这道题是求不固定长度区间的最大值，所以性质上是一样的，我们可以在双指针中指针移动的同时维护单调队列，单调队列的队头就是最大值，关于滑动窗口可以具体看这篇题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
int n;
int a[N], b[N];
int ans = 1e9 + 7;
int s;
int q[N];
signed main()
{
cin >> n >> s;
ll sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i + n] = a[i];
sum += a[i];
}
if (sum < s)
{
cout << -1;
return 0;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
b[i + n] = b[i];
}
sum = 0;
int hh = 0, tt = -1;
int l = 1;
for (int i = 1; i <= 2 * n; i++)
{
// 滑动窗口
// 由于区间总长度一定不能超过n，所以要判断一下
if (i - q[hh] >= n)
hh++;
while (hh <= tt && b[q[tt]] <= b[i])
tt--;
q[++tt] = i;
sum += a[i];
// s
while (sum - a[l] >= s)
{
sum -= a[l];
l++;
}
// 当我们现在求得区间得左端点比单调队列得队头端点大得话，需要让队头出列，知道队头在区间范围内为止
while (l > q[hh])
hh++;
if (sum >= s)
ans = min(ans, b[q[hh]]);
}
cout << ans;
return 0;
}好了，大家有疑问的话欢迎评论区留言哦！
