皇家守卫【算法赛】、百亿富翁、最大区间、附近最小

皇家守卫【算法赛】问题描述在蓝桥王国的边疆有 NN​ 座高塔每座高塔上均有一个士兵他们被称之为皇家守卫。每座高塔均有一个高度第 ii 座高塔的高度为 hihi​。对于第 ii 座塔若其右边存在某座塔 jj满足max⁡(hi,hi1,hi2,⋯,hj−1)hjmax(hi​,hi1​,hi2​,⋯,hj−1​)hj​则称第 jj 座塔为第 ii 座塔 暸望塔。现在王国传来 QQ 个任务每个任务会给定两个编号 x,yx,y需要你求解第 xx 座高塔和 第 yy 座高塔的公共 暸望塔 数量。x,yx,y 的公共 暸望塔 定义为两者同时拥有的 暸望塔。输入格式第一行输入两个整数 N,Q(1≤N,Q≤105)N,Q(1≤N,Q≤105) 表示高塔个数和任务数。第二行输入 NN 个整数 h1,h2,h3,⋯,hn(1≤hi≤109)h1​,h2​,h3​,⋯,hn​(1≤hi​≤109) 表示高塔的高度。接下来 QQ 行每行输入两个整数 x,y(1≤x≤y≤N)x,y(1≤x≤y≤N) 表示一次任务询问。输出格式输出 QQ 行每行一个整数表示答案输入样例5 3 1 3 4 5 7 1 3 2 4 3 5输出样例2 1 0说明对于第一个询问第 11 座高塔和第 33 座高塔的公共暸望塔有 4,54,5 号塔。暴力超时import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; public class Main { static int N 100010; static int a[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String g[] br.readLine().split( ); int nInteger.parseInt(g[0]),qInteger.parseInt(g[1]); g br.readLine().split( ); for (int i 1; i n; i) { a[i]Integer.parseInt(g[i-1]); } SetInteger set1new HashSet(); SetInteger set2new HashSet(); for (int i 0; i q; i) { g br.readLine().split( ); int uInteger.parseInt(g[0]),vInteger.parseInt(g[1]); valid(u,n,set1);valid(v,n,set2); long res0; for(int k1:set1){ for(int k2:set2){ if(k1k2)res; } } System.out.println(res); set1new HashSet();set2new HashSet(); } } static void valid(int x,int n,SetInteger set){ int pastMaxa[x]; for (int i x1; i n; i) { if(a[i]pastMax){ set.add(i); pastMaxa[i]; } } } }单调栈倍增优化import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { static int N 100010; static int a[]new int[N]; static int next[]new int[N];//表示右边第一个比我大的数的下标 static int len[]new int[N];//表示从i开始 暸望塔的数量 public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String g[] br.readLine().split( ); int nInteger.parseInt(g[0]),qInteger.parseInt(g[1]); g br.readLine().split( ); for (int i 1; i n; i) { a[i]Integer.parseInt(g[i-1]); } a[n1]Integer.MAX_VALUE;//哨兵 确保能找到右边比我大的数 StackInteger stacknew Stack();//维护一个单调递减的栈 for (int i n; i 1 ; i--) { int numa[i]; while(!stack.isEmpty() a[stack.peek()]num){//必须加等号 stack.pop(); } if(!stack.isEmpty())next[i]stack.peek(); else next[i]n1; stack.add(i); } next[n1] n1; // 需要这句 for (int i n; i 1; i--) { if(next[i]n){ len[i]len[next[i]]1; }else{ len[i]0; } } int k18; int go[][]new int[n2][k]; for (int i 1; i n1; i) { go[i][0]next[i]; } for (int j 1; j k; j) {//倍增表要求第二维在外层 for (int i 1; i n1; i) { go[i][j]go[go[i][j-1]][j-1]; } } for (int i 0; i q; i) { g br.readLine().split( ); int uInteger.parseInt(g[0]),vInteger.parseInt(g[1]); int uuu; int step0; for (int j k-1; j 0; j--) { if(go[u][j]v){ step1j; ugo[u][j]; } } System.out.println(len[uu]-step); } } }百亿富翁题目描述这天小明买彩票中了百亿奖金兴奋的他决定买下蓝桥公司旁的一排连续的楼房。已知这排楼房一共有 NN 栋编号分别为 1∼N1∼N第 ii 栋的高度为 hihi​。好奇的小明想知道对于每栋楼左边第一个比它高的楼房是哪个右边第一个比它高的楼房是哪个若不存在则输出 −1−1。但由于楼房数量太多小明无法用肉眼直接得到答案于是他花了 11 个亿来请你帮他解决问题你不会拒绝的对吧输入描述第 11 行输入一个整数 NN表示楼房的数量。第 22 行输入 NN 个整数相邻整数用空格隔开分别为 h1,h2,...,hNh1​,h2​,...,hN​表示楼房的高度。1≤N≤7×1051≤N≤7×1051≤hi≤1091≤hi​≤109。输出描述输出共两行。第一行输出 NN 个整数表示每栋楼左边第一栋比自己高的楼的编号。第二行输出 NN 个整数表示每栋楼右边第一栋比自己高的楼的编号。输入输出样例示例 1输入5 3 1 2 5 4输出-1 1 1 -1 4 4 3 4 -1 -1import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; public class Main { static int N 7*100010; static int a[]new int[N]; static int left[]new int[N];//表示左边边第一个比我大的数的下标 static int right[]new int[N];//表示左边边第一个比我大的数的下标 public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // String g[] br.readLine().split( ); int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); for (int i 0; i n; i) { a[i]Integer.parseInt(g[i]); } //维护一个单调递减的栈 StackInteger stacknew Stack(); for (int i 0; i n; i) { while(!stack.isEmpty() a[stack.peek()]a[i])stack.pop(); if(!stack.isEmpty())left[i]stack.peek(); else left[i]-1; stack.add(i); } StackInteger stack1new Stack(); for (int i n-1; i0; i--) { while(!stack1.isEmpty() a[stack1.peek()]a[i])stack1.pop(); if(!stack1.isEmpty())right[i]stack1.peek(); else right[i]-1; stack1.add(i); } for (int i 0; i n; i) { if(left[i]!-1)System.out.print(left[i]1 ); else System.out.print(-1 ); } System.out.println(); for (int i 0; i n; i) { if(right[i]!-1)System.out.print(right[i]1 ); else System.out.print(-1 ); } } }最大区间问题描述给定一个长度为 nn 的序列 AiAi​求 L,RL,R 使 (R−L1)⋅min⁡(AL,AL1,…,AR)(R−L1)⋅min(AL​,AL1​,…,AR​) 尽可能大其中 min⁡min 表示最小值。你只需要输出最大的值即可不需要输出具体的 L,RL,R。输入格式输入的第一行包含一个整数 nn。第二行包含 nn 个整数分别表示 A1,A2,…,AnA1​,A2​,…,An​相邻两个整数之间使用一个空格分隔。输出格式输出一行包含一个整数表示答案。样例输入5 1 1 3 3 1样例输出6评测用例规模与约定对于 40%40% 的评测用例1≤n≤50001≤n≤50001≤Ai≤50001≤Ai​≤5000对于所有评测用例1≤n≤3×1051≤n≤3×1051≤Ai≤1091≤Ai​≤109。单调队列超时import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N 3*100010; static int a[]new int[N]; static int q[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // String g[] br.readLine().split( ); int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); for (int i 0; i n; i) { a[i]Integer.parseInt(g[i]); } int head0,tail0; //维护一个单调递增队列队列 long resLong.MIN_VALUE; for (int k 1; k n; k) {//滑动窗口的大小 head0;tail0; for (int i 0; i n; i) { if(i-q[head]k)head; while(tail-head0 a[q[tail-1]]a[i])tail--; q[tail]i; if(ik-1)resMath.max(res,(long)k*a[q[head]]);// 此句条件一定不要忘 } } System.out.println(res); } }单调栈import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.Thread.State; import java.util.Stack; public class Main { static int N 3*100010; static int a[]new int[N]; static int right[]new int[N]; static int left[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // String g[] br.readLine().split( ); int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); for (int i 0; i n; i) { a[i]Integer.parseInt(g[i]); } //维护一个单调递增栈 //对于每一个数 向左右扩展找到第一个小于我的数 StackInteger stacknew Stack(); for (int i 0; i n; i) { while(!stack.isEmpty() a[stack.peek()]a[i])stack.pop(); if(!stack.isEmpty())left[i]stack.peek(); else left[i]-1; stack.add(i); } StackInteger stack1new Stack(); for (int i n-1; i 0; i--) { while(!stack1.isEmpty() a[stack1.peek()]a[i])stack1.pop(); if(!stack1.isEmpty())right[i]stack1.peek(); else right[i]n; stack1.add(i); } long resLong.MIN_VALUE; for (int i 0; i n; i) { //System.out.println(left[i] right[i]); resMath.max(res,(long)(right[i]-left[i]-1)*a[i]); } System.out.println(res); } }附近最小问题描述小蓝有一个序列 a[1],a[2],...,a[n]a[1],a[2],...,a[n]。给定一个正整数 kk请问对于每一个 11 到 nn 之间的序号 iia[i−k],a[i−k1],...,a[ik]a[i−k],a[i−k1],...,a[ik] 这 2k12k1 个数中的最小值是多少当某个下标超过 11 到 nn 的范围时数不存在求最小值时只取存在的那些值。输入格式输入的第一行包含一整数 nn。第二行包含 nn 个整数分别表示 a[1],a[2],...,a[n]a[1],a[2],...,a[n]。第三行包含一个整数 kk 。输出格式输出一行包含 nn 个整数分别表示对于每个序号求得的最小值。样例输入样例输出2 2 2 3 3评测用例规模与约定对于 30% 的评测用例1n10001a[i]10001n10001a[i]1000。对于 50% 的评测用例1n100001a[i]100001n100001a[i]10000。对于所有评测用例1n10000001a[i]10000001n10000001a[i]1000000。import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N 2*1000010; static int a[]new int[N],ind; static int q[]new int[N]; static int res[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // String g[] br.readLine().split( ); int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); int kInteger.parseInt(br.readLine()); int kkk; for (int i 0; i k; i) { a[ind]Integer.MAX_VALUE; } for (int i 0; i n; i) { a[ind]Integer.parseInt(g[i]); } for (int i 0; i k; i) { a[ind]Integer.MAX_VALUE; } k2*k1; //维护一个单调递增的队列 int tail0,head0; for (int i 0; i ind; i) { if(tail-head0 i-q[head]k)head; while(tail-head0 a[q[tail-1]]a[i])tail--; q[tail]i; if(ik-1)res[i]a[q[head]]; } for (int i k-1 ; i kn-1; i) { System.out.print(res[i] ); } } }import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N 2*1000010; static int a[]new int[N],ind; static int q[]new int[N]; static int res[]new int[N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // String g[] br.readLine().split( ); int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); int kInteger.parseInt(br.readLine()); for (int i 0; i n; i) { a[i]Integer.parseInt(g[i]); } //维护一个单调递增的队列 int tail0,head0,r-1;//要添加一次左边界的最大值 for (int i 0; i n; i) { int leftMath.max(0, i-k); int rightMath.min(n-1, ik); while(tail-head0 q[head]left)head; while (r right) { r; while (tail - head 0 a[q[tail - 1]] a[r]) tail--; q[tail] r; } res[ind]a[q[head]]; } for (int i 0; i ind; i) { System.out.print(res[i] ); } } }