## 算法訓練 區間k大數查詢 ?
時間限制:1.0s ? 內存限制:256.0MB
?
問題描述
給定一個序列,每次詢問序列中第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),序列中的數<=106。
~~~
// k 大數查詢
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001],brr[1001];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int n,m;
int l,r,k;
int i,j;
while(cin>>n)
{
for(i=0;i<n;++i)
cin>>arr[i];
cin>>m;
while(m--)
{
cin>>l>>r>>k;
// 將相應的區間復制到另一個數組中,排序
for(j=l-1,i=0;j<r;++j,++i)
brr[i]=arr[j];
sort(brr,brr+i,cmp);
cout<<brr[k-1]<<endl;
}
}
return 0;
}
~~~
- 前言
- 入門訓練四道題
- 基礎練習之閏年判斷——BASIC-1
- 基礎練習之01字串——BASIC-2
- 基礎練習之字母圖形——BASIC-3
- 基礎練習之數列特征——BASIC-4
- 基礎練習之查找整除——BASIC-5
- 基礎練習之楊輝三角形——BASIC-6
- 基礎練習之特殊的數字——BASIC-7
- 基礎練習之回文數——BASIC-8
- 基礎練習之特殊回文數——BASIC-9
- 基礎練習之十進制轉十六進制——BASIC-10
- 基礎練習之十六進制轉十進制——BASIC-11
- 基礎練習之十六進制轉八進制——BASIC-12
- 基礎練習之數列排序——BASIC-13
- 算法訓練之區間K大數查詢——ALGO-1
- 算法訓練之最大最小公倍數——ALGO-2
- 藍橋杯-代碼填空之一
- 藍橋杯-代碼填空之二
- 藍橋杯-代碼填空之三
- 藍橋杯-代碼填空之精品
- 藍橋杯-歷屆試題之翻硬幣
- 藍橋杯-代碼填空之四
- 藍橋杯-結果填空題
- 藍橋杯-結果填空之排座位
- 藍橋杯-歷屆試題之大臣的旅費