2022/11/23:修改了一下代码。
题意
有 \(T\) 组数据,每次给出一个 \(n,q\),表示台阶的数量和询问的次数。
然后再给出一个 \(a_i\) 为台阶高度的差分数组。
每次询问给出一个 \(k\),表示每次能走 \(k\) 个单位的高度。
问:最高能到达的高度。
思路
考虑暴力,我们知道了高度的差分数组,那么我们就可以直接算出当前的高度。然后,直接暴力即可。
但是,这样的时间复杂度是不对的,为:\(O(Tqn)\) 的,显然会超时,那么我们只有想一想优化了。
因为对于每一个 \(a_i\),\(1 \leq a_i\) 的,所以,我们的高度是单调递增的。因此,我们可以用二分的方法来优化。
我们可以用一个数组 \(c\) 维护 \(a_1 \sim a_i\) 最大值,因为我们的操作中,如果你能走到 \(i\),那么你一定能走过 \(1 \sim i\) 的台阶,而对我们最有限制的便是 \(\max(a_i)\)。
最后,再来分析一下时间复杂度为:\(O(Tq\log n)\) 的,不会超时。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int T,n,q,k;
int arr[N],c[N],s[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
signed main(){
T = read();
while (T--){
n = read();
q = read();
for (int i = 1;i <= n;i++){
arr[i] = read();
c[i] = max(c[i - 1],arr[i]);//max(a[i])
s[i] = s[i - 1] + arr[i];//差分数组的前缀和就为当前的值
}
while (q--){
k = read();
int l = 0,r = n;//二分板子
while (l <= r){
int mid = l + r >> 1;
if (c[mid] > k) r = mid - 1;//重点
else l = mid + 1;
}
printf("%lld ",s[l - 1]);//输出
}
puts("");
}
return 0;
}
标签:Scuza,int,题解,高度,mid,CF1742E,数组,我们
From: https://www.cnblogs.com/WaterSun/p/18264808