Областная олимпиада по информатике, 2018 год, 10-11 класс
Два элемента массива $a_i$, $a_j$ с индексами $(i, j)$ $1 \le i < j \le n$, могут образовать пару и силой этой пары назовем $a_i + a_j$. Найдите силу пары, являющейся $k$-й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа $n$ и $k$ ($1 \le k \le \frac{n * (n - 1)}{2}$).Во второй строке через пробел заданы целые числа $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 10^6$).
Формат выходных данных:
Выведите ответ на задачу.Примеры:
1.Вход:3 3 7 1 4Ответ:
112.Вход:
5 7 1 5 3 5 3Ответ:
83.Вход:
10 32 0 0 0 0 0 0 0 0 0 0Ответ:
04.Вход:
9 15 5 6 3 0 0 4 1 4 1Ответ:
5
Замечание:
В первом примере можно сделать три пары с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_2$ + $a_3$} = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.Во втором примере можно сделать десять пар с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_1$ + $a_4$, $a_1$ + $a_5$, $a_2$ + $a_3$, $a_2$ + $a_4$, $a_2$ + $a_5$, $a_3$ + $a_4$, $a_3$ + $a_5$, $a_4$ + $a_5$} = {1 + 5, 1 + 3, 1 + 5, 1 + 3, 5 + 3, 5 + 5, 5 + 3, 3 + 5, 3 + 3, 5 + 3} = {6, 4, 6, 4, 8, 10, 8, 8, 6, 8}. Если их отсортировать по неубыванию силы, то получится {4, 4, 6, 6, 6, 8, 8, 8, 8, 10} и седьмой элемент это 8.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.Ограничения которые присутствуют в тестах:
- 10 тестов: $2 \le n \le 10^3$
- 20 тестов: $2 \le n \le 10^4$
- 20 тестов: $2 \le n \le 10^5$
Комментарий/решение:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
int a[n];
vector<int> b;
for(int i = 0; i<n; i++){
cin >> a[i];
}
for(int i = 0; i<n-1; i++){
for(int j = i+1; j<n; j++){
b.push_back(a[i]+a[j]);
}
}
sort(b.begin(), b.end());
cout << b[k-1];
}
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
const ll inf = 1e9 + 123;
const ll N = 1e5 + 123;
const ll mod = 1e9 + 7;
ll n,k,a[N];
ll get(int x){
ll cnt = 0;
for(int j = 1; j <= n; ++j){
int l = 1, r = j - 1, ind = 0;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] + a[j] <= x){
ind = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cnt += ind;
}
return cnt;
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
sort(a + 1, a + n + 1);
ll l = 0, r = 2000000, ans;
while(l <= r){
ll mid = (l + r) / 2;
if(get(mid) >= k){
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans;
}
Не знаю разрешены ли библиотеки, но эта встроенная
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.