第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
算法训练 区间k大数查询
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。
输入格式
第一行包含一个数n，表示序列长度。
第二行包含n个正整数，表示给定的序列。
第三个包含一个正整数m，表示询问个数。
接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。
输出格式
总共输出m行，每行一个数，表示询问的答案。
样例输入
5
1 2 3 4 5
2
1 5 2
2 3 2
样例输出
4
2
数据规模与约定
对于30%的数据，n,m<=100；
对于100%的数据，n,m<=1000；
保证k<=(r-l+1)，序列中的数<=10^6
题解：
C语言
#include <stdio.h> #include <stdlib.h> int Split(int *data,int pre,int rear) { int value=data[pre]; while(pre<rear) { while(data[rear]>=value && pre<rear) rear--; data[pre]=data[rear]; while(data[pre]<value && pre<rear) pre++; data[rear]=data[pre]; } data[pre]=value; return pre; } //快速排序 void QuickSort(int *data,int pre,int rear,int k) { if(pre<=rear) { int mid=Split(data,pre,rear); if(mid==k) { printf("%d\n",data[mid]); } else if(mid>k) { QuickSort(data,pre,mid-1,k); } else { QuickSort(data,mid+1,rear,k); } } } void Copy(int *data,int n,int *temp) { int i; for(i=0;i<n;i++) { temp[i]=data[i]; } } int main() { int i; int n; int m; int *data; scanf("%d",&n); data=(int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) { scanf("%d",&data[i]); } scanf("%d",&m); while(m) { int pre; int rear; int k; int *temp=(int *)malloc(sizeof(int)*n); scanf("%d%d%d",&pre,&rear,&k); Copy(data,n,temp); QuickSort(temp,pre-1,rear-1,rear-k); m--; } return 0; }
C++语言
#include<stdio.h> #include<algorithm> using namespace std; #define N 10005 int n,m; int a[N],tree[15][N],sum[15][N]; bool cmp(int x,int y) { return x>y; } void build(int x,int L,int R) { if(L==R) return; int i; int mid=(L+R)>>1; int lp=L,rp=mid+1,l=mid-L+1; for(i=L;i<=R;i++) if(tree[x][i]>a[mid]) l--; for(i=L;i<=R;i++) { sum[x][i]=i==L?0:sum[x][i-1]; if(a[mid]==tree[x][i] && l) { l--; tree[x+1][lp++]=tree[x][i]; sum[x][i]++; } else if(tree[x][i]>a[mid]) { tree[x+1][lp++]=tree[x][i]; sum[x][i]++; } else tree[x+1][rp++]=tree[x][i]; } build(x+1,L,mid); build(x+1,mid+1,R); } int query(int x,int L,int R,int l,int r,int k) { if(l==r) return tree[x][l]; int mid=(L+R)>>1; int t,tt; t=l==L?0:sum[x][l-1]; tt=sum[x][r]-t; if(k<=tt) return query(x+1,L,mid,L+t,L+t+tt-1,k); else return query(x+1,mid+1,R,mid-L+1+l-t,mid-L+1+r-t-tt,k-tt); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); tree[0][i]=a[i]; } sort(a+1,a+1+n,cmp); build(0,1,n); scanf("%d",&m); int l,r,k; while(m--) { scanf("%d%d%d",&l,&r,&k); printf("%d\n",query(0,1,n,l,r,k)); } return 0; }
Java语言
这里看好扫描器的使用啊，数据录入不是很方便。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { int n = Integer.parseInt(br.readLine()); int[] arr = new int[n+1]; String[] s = br.readLine().split(" "); for (int i = 1; i < arr.length; i++) { arr[i] = Integer.parseInt(s[i-1]); } int m = Integer.parseInt(br.readLine()); String[] s1; int[][] brr = new int[m][3]; for (int i = 0; i < m; i++) { s1 = br.readLine().split(" "); for (int j = 0; j < s1.length; j++) { brr[i][j] = Integer.parseInt(s1[j]); } } int a; int b; int c; for (int i = 0; i < m; i++) { a = brr[i][0]; b = brr[i][1]; c = brr[i][2] - 1; int[] brr1 = new int[b - a + 1]; System.arraycopy(arr, a, brr1, 0, b - a + 1); shellSort(brr1); System.out.println(brr1[b - a - c]); } } catch (IOException e) { e.printStackTrace(); }finally { try { br.close(); } catch (IOException e) { e.printStackTrace(); } } } public static void shellSort(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } } } }
Python语言
我们已经不是1次两次看到列表推导式了，应该已经不陌生了，有时间可以专门的捉摸一下列表推导式，很方便好用。
n = input() n_list = list(map(int,input().split())) m = int(input()) Ls = [] for i in range(m): Ls.append(list(map(int,input().split()))) for j in Ls: l=int(j[0])-1 r=int(j[1]) k=int(j[2])- 1 result = sorted(n_list[l:r],reverse=True) print(result[k])
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
