You've got another problem dealing with arrays. Let's consider an arbitrary sequence containing n (not necessarily different) integers a1, a2, ..., an. We are interested in all possible pairs of numbers (ai, aj), (1?≤?i,?j?≤?n). In other words, let's consider all n2 pairs of numbers, picked from the given array.
For example, in sequence a?=?{3,?1,?5} are 9 pairs of numbers: (3,?3),?(3,?1),?(3,?5),?(1,?3),?(1,?1),?(1,?5),?(5,?3),?(5,?1),?(5,?5).
Let's sort all resulting pairs lexicographically by non-decreasing. Let us remind you that pair (p1, q1) is lexicographically less than pair (p2, q2) only if either p1< p2, or p1 = p2 and q1 < q2.
Then the sequence, mentioned above, will be sorted like that: (1,?1),?(1,?3),?(1,?5),?(3,?1),?(3,?3),?(3,?5),?(5,?1),?(5,?3),?(5,?5)
Let's number all the pair in the sorted list from 1 to n2. Your task is formulated like this: you should find the k-th pair in the ordered list of all possible pairs of the array you've been given.
The first line contains two integers n and k (1?≤?n?≤?105,?1?≤?k?≤?n2). The second line contains the array containing n integers a1, a2, ..., an (?-?109?≤?ai?≤?109). The numbers in the array can coincide. All numbers are separated with spaces.
Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout, streams or the %I64d specificator instead.
In the single line print two numbers — the sought k-th pair.
2 4 2 1
2 2
3 2 3 1 5
1 3
In the first sample the sorted sequence for the given array looks as: (1,?1),?(1,?2),?(2,?1),?(2,?2). The 4-th of them is pair (2,?2).
The sorted sequence for the array from the second sample is given in the statement. The 2-nd pair there is (1,?3).
题解：
如果这题没重复数据可以发现先从小到大sort一下，第一个数字为第(k%n==0)?k/n-1:k/n 这个式子算出的下标，第二个会是(k-1+n)%n的下标
第一次直接用取模找的规律到第3组就wa了，仔细想想发现当输入数据有重复的时候找规律直接输出会出错，这个时候要特殊处理一遍
可以发现用取模的方法得到的第一个数字一定是对的，那么我就用num记录数组中和算出的第一个数字相同的个数，用st记录下算出的第一个数字的前一个不同种数字的位置，
这么做是有原因的，因为一直到st前面的排序都是对的，那么我们就把k处理一下，后面的由于算出的第一个数字在数组中有相同的时候会有些pair后面的那个数字更小但是后算出来，这样是错的，这个时候要对后面进行重新排序，pair第一个数字设算出的为x，在数组中的数目为num，那么对于数组中的每一个数字都应该放num个，这样的话同样用取模的方法很快可以算出第二个的下标。。这个不太好说要体会一下，还有就是有些特殊情况要特判
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#include<stdio.h>
using namespace std;
#define ll long long
ll a[100005];
map<ll,ll>p;
int main()
{ll n,k,i,j,temp;scanf("%I64d%I64d",&n,&k);for(i=0;i<n;i++){scanf("%I64d",&a[i]);p[a[i]]=p[a[i]]+1;}temp=k;sort(a,a+n);int t=(k%n==0)?k/n-1:k/n;printf("%I64d",a[t]);int num=1,ans;int st=t;for(i=t-1;i>=0;i--){if(a[i]==a[i+1]){st=i;}elsebreak;}k-=(st)*n;for(i=st+1;i<n;i++){if(a[i]==a[i-1]){num++;}elsebreak;}if(num==1){printf(" %I64d\n",a[(temp-1+n)%n]);}elseprintf(" %I64d\n",a[k%num==0?k/num-1:k/num]);return 0;
}