皇家守卫【算法赛】、百亿富翁、最大区间、附近最小
皇家守卫【算法赛】
问题描述
在蓝桥王国的边疆有 NN 座高塔，每座高塔上均有一个士兵，他们被称之为皇家守卫。
每座高塔均有一个高度，第 ii 座高塔的高度为 hihi。对于第 ii 座塔，若其右边存在某座塔 jj，满足：max(hi,hi+1,hi+2,⋯,hj−1)<hjmax(hi,hi+1,hi+2,⋯,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 n=Integer.parseInt(g[0]),q=Integer.parseInt(g[1]); g = br.readLine().split(" "); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(g[i-1]); } Set<Integer> set1=new HashSet<>(); Set<Integer> set2=new HashSet<>(); for (int i = 0; i < q; i++) { g = br.readLine().split(" "); int u=Integer.parseInt(g[0]),v=Integer.parseInt(g[1]); valid(u,n,set1);valid(v,n,set2); long res=0; for(int k1:set1){ for(int k2:set2){ if(k1==k2)res++; } } System.out.println(res); set1=new HashSet<>();set2=new HashSet<>(); } } static void valid(int x,int n,Set<Integer> set){ int pastMax=a[x]; for (int i = x+1; i <= n; i++) { if(a[i]>pastMax){ set.add(i); pastMax=a[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 n=Integer.parseInt(g[0]),q=Integer.parseInt(g[1]); g = br.readLine().split(" "); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(g[i-1]); } a[n+1]=Integer.MAX_VALUE;//哨兵 确保能找到右边比我大的数 Stack<Integer> stack=new Stack<>();//维护一个单调递减的栈 for (int i = n; i >=1 ; i--) { int num=a[i]; while(!stack.isEmpty() && a[stack.peek()]<=num){//必须加等号 stack.pop(); } if(!stack.isEmpty())next[i]=stack.peek(); else next[i]=n+1; stack.add(i); } next[n+1] = n+1; // 需要这句 for (int i = n; i >= 1; i--) { if(next[i]<=n){ len[i]=len[next[i]]+1; }else{ len[i]=0; } } int k=18; int go[][]=new int[n+2][k]; for (int i = 1; i <= n+1; i++) { go[i][0]=next[i]; } for (int j = 1; j < k; j++) {//倍增表要求第二维在外层 for (int i = 1; i <= n+1; i++) { go[i][j]=go[go[i][j-1]][j-1]; } } for (int i = 0; i < q; i++) { g = br.readLine().split(" "); int u=Integer.parseInt(g[0]),v=Integer.parseInt(g[1]); int uu=u; int step=0; for (int j = k-1; j >=0; j--) { if(go[u][j]<=v){ step+=1<<j; u=go[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×105，1≤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 n=Integer.parseInt(br.readLine()); String g[] = br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } //维护一个单调递减的栈 Stack<Integer> stack=new 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); } Stack<Integer> stack1=new 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]=-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−L+1)⋅min(AL,AL+1,…,AR)(R−L+1)⋅min(AL,AL+1,…,AR) 尽可能大，其中 minmin 表示最小值。
你只需要输出最大的值即可，不需要输出具体的 L,RL,R。
输入格式
输入的第一行包含一个整数 nn。
第二行包含 nn 个整数，分别表示 A1,A2,…,AnA1,A2,…,An，相邻两个整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5 1 1 3 3 1样例输出
6评测用例规模与约定
对于 40%40% 的评测用例，1≤n≤50001≤n≤5000，1≤Ai≤50001≤Ai≤5000；
对于所有评测用例，1≤n≤3×1051≤n≤3×105，1≤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 n=Integer.parseInt(br.readLine()); String g[] = br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } int head=0,tail=0; //维护一个单调递增队列队列 long res=Long.MIN_VALUE; for (int k = 1; k <= n; k++) {//滑动窗口的大小 head=0;tail=0; for (int i = 0; i < n; i++) { if(i-q[head]>=k)head++; while(tail-head>0 && a[q[tail-1]]>=a[i])tail--; q[tail++]=i; if(i>=k-1)res=Math.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 n=Integer.parseInt(br.readLine()); String g[] = br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } //维护一个单调递增栈 //对于每一个数 向左右扩展找到第一个小于我的数 Stack<Integer> stack=new 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); } Stack<Integer> stack1=new 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 res=Long.MIN_VALUE; for (int i = 0; i < n; i++) { //System.out.println(left[i]+" "+right[i]); res=Math.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 之间的序号 ii，a[i−k],a[i−k+1],...,a[i+k]a[i−k],a[i−k+1],...,a[i+k] 这 2k+12k+1 个数中的最小值是多少？
当某个下标超过 11 到 nn 的范围时，数不存在，求最小值时只取存在的那些值。
输入格式
输入的第一行包含一整数 nn。
第二行包含 nn 个整数，分别表示 a[1],a[2],...,a[n]a[1],a[2],...,a[n]。
第三行包含一个整数 kk 。
输出格式
输出一行，包含 nn 个整数，分别表示对于每个序号求得的最小值。
样例输入
样例输出
2 2 2 3 3评测用例规模与约定
对于 30% 的评测用例，1<=n<=1000，1<=a[i]<=10001<=n<=1000，1<=a[i]<=1000。
对于 50% 的评测用例，1<=n<=10000，1<=a[i]<=100001<=n<=10000，1<=a[i]<=10000。
对于所有评测用例，1<=n<=1000000，1<=a[i]<=10000001<=n<=1000000，1<=a[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 n=Integer.parseInt(br.readLine()); String g[] = br.readLine().split(" "); int k=Integer.parseInt(br.readLine()); int kk=k; 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; } k=2*k+1; //维护一个单调递增的队列 int tail=0,head=0; for (int i = 0; i < ind; i++) { if(tail-head>0 && i-q[head]>=k)head++; while(tail-head>0 && a[q[tail-1]]>=a[i])tail--; q[tail++]=i; if(i>=k-1)res[i]=a[q[head]]; } for (int i = k-1 ; i < k+n-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 n=Integer.parseInt(br.readLine()); String g[] = br.readLine().split(" "); int k=Integer.parseInt(br.readLine()); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(g[i]); } //维护一个单调递增的队列 int tail=0,head=0,r=-1;//要添加一次左边界的最大值 for (int i = 0; i < n; i++) { int left=Math.max(0, i-k); int right=Math.min(n-1, i+k); while(tail-head>0 && 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]+" "); } } }