本文主要是介绍njupt（1406-第K小的数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第K小的数
总提交 : 101 测试通过 : 30
比赛描述
你为SKZ公司的数据结构部门工作，你的工作是重新写一个程序，这个程序能快速地找到一段数列中第k小的数。
就是说，给定一个整数数列a[1..n]，其中每个元素都不相同，你的程序要能回答一组格式为Q (i , j , k)的查询，Q(i, j ,k)的意思是“在a[i..j]中第k小的数是多少？”
例如令 a = {1, 5, 2, 6, 3, 7, 4}，查询格式为Q (2 , 5 , 3)，数列段a[2..5] = {5, 2, 6, 3}，第3小的数是5，所以答案是5。
输入
第一行包括一个正整数n，代表数列的总长度，还有一个数m，代表有m个查询。n、m满足：1≤n≤100 000，1≤m≤5 000。
第二行有n个数，代表数列的元素，所有数都不相同，而且不会超过109 。
接下来有m行，每行三个整数i、j、k，代表一次查询，i、j、k满足：1≤i≤j≤n， 1≤k≤j−i+1。
输出
输出每个查询的答案，用换行符隔开。
样例输入
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
样例输出
5
6
3
http://blog.csdn.net/v_JULY_v/article/details/6452100
#include<iostream>
#include<algorithm>
using namespace std; struct node{ int num,data; bool operator < (const node &p) const { return data < p.data; }
};
node p[100001]; int main()
{ int n,m,i,j,a,b,c;while(scanf("%d %d",&n,&m)!=EOF) { for(i=1;i<=n;i++) { scanf("%d",&p[i].data); p[i].num = i; } sort(p+1,p+1+n); for(j=1;j<=m;j++) { scanf("%d %d %d",&a,&b,&c); for(i=1;i<=n;i++) { if(p[i].num>=a && p[i].num<=b) c--; if(c == 0) break; } printf("%d\n",p[i].data); } } return 0;
}
这篇关于njupt（1406-第K小的数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
