C.Find Pair（codeforces）

Find Pair

问题：给出一个序列集S，对于<x, y> ，x 在S中， y也在S中，按字典序排列，求第k个<x, y>。

例子：1 2 3（n = 3）

我们取第k个<x, y>。

我刚开始直接暴力（Tle了）

再想到下面的。

按顺序排列，每个数字组成n个 <x, y>。我们可以发现（k-1）/ n 为第一个数字x（刚开始想的是k/n，发现不行）。再有点野心试试可以用 k 和 n 找到第二个数字y，就有了（k-1）% n 是y。

我又兴高采烈的去交，还交了不止一发（wa了）

又有想到了有重复元素的情况，再来个例子：1 1 2 3（n = 4）.

然后就去重，循环，各种乱七八糟的（Tle了）

再来，找每个元素的个数，去重，确定<x, y>的第一个元素x，除去第一个元素x之前的元素组成的<x, y>（k-前面元素个数 * n）。再然后就遍历确定第二个元素（k – 用第一个元素个数 * 各个元素的个数，直到 k <= 0）

[code]#include<bits/stdc++.h>#define ll long longusing namespace std;ll s[100010], t[100010];char u[20], v[20];map<int, int> M;int main() {ll n, m, w, r;scanf(\"%I64d%I64d\", &n, &m);for(int i=0; i<n; i++) {scanf(\"%I64d\", &s[i]);M[s[i]]++;}sort(s, s+n);ll x = s[(m-1)/n];//去重ll con = unique(s, s+n) - s;//如果相等表面没有重复元素if(n == con) {printf(\"%I64d %I64d\", x, s[(m-1)%n]);}else {//打印第一个元素printf(\"%I64d \",  x);//确定x之前有多少个不同的元素，和x的个数ll k = lower_bound(s, s+con, x) - s, r = M[s[k]];//除去x之前元素组成的<x, y>for(int i=0; i<k; i++) m -= M[s[i]]*n;////找第二个元素for(int i=0; i<con; i++) {if(m > 0) {m -= r*M[s[i]];}if(m <= 0) {printf(\"%I64d\", s[i]);break;}}}return 0;}