题目链接
吃水果-小红书2024笔试(codefun2000)
题目内容
在一个遥远的星球上,这颗星球上的果树非常奇特,同一条直线上的果树只会长出不同种类的水果。有一天塔子哥乘飞船来到了这里,由于他的食物不多了,于是他决定在这颗星球上进行补给。他发现了一个 n 棵果树长成的直线,其中第 i 棵果树上有 ai个第 i 种水果。
塔子哥想要品尝一部分这些独特的水果,现在塔子哥可以对这个水果序列进行最多 k 次操作,每次可选择一个连续的区间将其中的水果全部吃掉,但剩余的水果种类必须大于 0 。塔子哥知道,这个星球上的水果都非常美味,每一种都有独特的口感和香味。塔子哥不想错过任何一种美味的水果,所以塔子哥希望在吃掉一些水果后,剩余水果中数量最少的那种尽可能多,以便在未来能够继续享用美味的水果。
现在问题来了:在上述情况下,剩余水果中数量最少的那种最多能有多少呢?
输入描述
输出描述
输出仅包含一个正整数,表示答案。
样例1
输入
5 1
45 39 90 65 15
输出
45
样例1解释
题解1
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int N = 1e5 + 10;
/*
L[i]=1表示区间[1,i-1]内存在比a[i]小的元素
R[i]=1表示区间[i+1, n]内存在比a[i]小的元素
*/
int n, k, ans, a[N], L[N], R[N], minn;
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
minn = a[1];
for(int i = 1; i <= n; i++){ // 这里,minn表示区间[1,i-1]中的最小值
if(a[i] > minn) L[i] = 1;
minn = min(minn, a[i]);
}
minn = a[n];
for(int i = n; i > 0; i--){ // 这里,minn表示区间[i+1, n]中的最小值
if(a[i] > minn) R[i] = 1;
minn = min(minn, a[i]);
}
for(int i = 1; i <= n; i++){
if(L[i] + R[i] <= k) ans = max(ans, a[i]);
}
printf("%d\n", ans);
return 0;
}
标签:水果,minn,小红书,塔子哥,2024,int,区间,星球,codefun2000
From: https://blog.csdn.net/qq_45332149/article/details/140679329