小工具知识网

当前位置: 首页 > 行业知识 > 李渊的准备

行业知识

李渊的准备

2026-11-22 09:06:26 来源:互联网转载

(���题所提到历史与真实历史无关,请勿直接带入) 唐高祖李渊是一位非常杰出的军事统帅,他的儿子李世民更是有着出众的领导能力,开创了贞观之治!

()

俗话说,兵马未动,粮草先行。为了能够顺利推翻隋炀帝的统治,李渊决定去检查下粮仓的情况。现有 n 个大小不等的粮仓(按照从1到n进行编号),第 i 个粮仓里存放 AiA_iAi​ (单位)的粮食。

为了检验当前是否能够出兵,李渊对李世民提出了 T 次询问。

()

每次询问的内容是,从粮仓LLL到粮仓RRR,其中储量最多的粮仓,能否满足这次的战争需求 q (即 AiA_iAi​ >= q)。

记忆超群的李世民一下子就能知道这些粮仓之中储量多少,不过为了考验你的才能,他决定让你来回答。

输入描述:

 
第一行: n t q 分别表示粮仓的数量,询问的次数,战争的需求 第二行 n 个整数AiA_iAi​,表示粮仓的储量 接下来t行,每行为一个询问,两个整数L和R,分别表示询问的区间编号

输出描述:

 
对于t次询问 每行输出区间最大值以及 YES 或 NO 表示能或者不难满足战争需求(中间用一个空格隔开)

示例1

输入

复制6 4 5 4 5 8 1 2 6 1 1 2 3 4 5 1 4

6 4 54 5 8 1 2 61 12 34 51 4

输出

复制4 NO 8 YES 2 NO 8 YES

4 NO8 YES2 NO8 YES

备注:

1 ≤ n,t ≤ 2e5 1 ≤ qqq,AiA_iAi​ ≤ 2e5 1 ≤ L ≤ R ≤ n 

想法:

这题不考虑时间复杂度还是很好写的,就是多次询问区间最大值,可惜不考虑时间复杂度是不行的。我总感觉可以用类似前缀和的思想来写,结果想不到,想到了另一种。就是开另一个数组来存粮仓,然后从大到小排序。询问就遍历n个粮仓,如果没排序前的下标在l到r的范围内,就是最大值了,就可以break了。暴力就是从a[l]到a[r]遍历,打擂台求最大值。

代码:

#includeusing namespace std;int n,q,m;int a[200010];struct ty{    int idx,num;}b[200010];bool cmp(ty a,ty b){    return a.num>b.num;}int main(){    scanf("%d%d%d",&n,&q,&m);    for(int i=1;i

上一篇:Labview打地鼠游戏制作教程,从零开始,步步为赢!

下一篇:王者荣耀的服务器怎么选?