Find Pair

发表于 分类于 ，

    给出n个数，求这n个数的任意两个的组合的数对中第k小的一对。

Find Pair

Created by LXC on Thu Jun 15 11:01:08 2023

https://codeforces.com/problemset/problem/160/C

ranting: 1700

tag: implementation, math, sortings

problem

给出n个数，求这n个数的任意两个的组合的数对中第k小的一对。

solution

n个数的索引从0到n-1，我们将k-=1.

n个数完全不同则可以用(a[k/n],a[k%n])作为答案。

但是n个数会有重复，可以确定的是数对的第一个数是a[k/n]，我们找出第一个数比a[k/n]小的数对的个数，在用k减去它，得到以a[k/n]作为第一个数的数对个数m。a[k/n]在n个数中出现了c次，那么答案就是(a[k/n], a[m/c])

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, k;
    cin >> n >> k;
    k--;
    vector<ll> a(n);
    map<ll, int> mp;
    for (ll& i : a)
        cin >> i, mp[i]++;
    sort(a.begin(), a.end());
    ll s = k / n, e = s;
    while (s != -1 && a[s] == a[e])
        s--;
    ll m = k - (s + 1) * n;
    // cout << m << " " << mp[a[e]] << "\n";
    cout << a[k / n] << " " << a[m / mp[a[e]]] << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}