Областная олимпиада по информатике, 2018 год, 9 класс
(k-я пара) Вам задан массив a, состоящий из n целых чисел a1, a2, ..., an.
Два элемента массива ai, aj с индексами (i,j) 1≤i<j≤n, могут образовать пару и силой этой пары назовем ai+aj. Найдите силу пары, являющейся k-й по счету, если отсортировать все пары по неубыванию силы.
Во второй строке через пробел заданы целые числа a1, a2, ..., an (0≤ai≤106).
Во втором примере можно сделать десять пар с силами {a1 + a2, a1 + a3, a1 + a4, a1 + a5, a2 + a3, a2 + a4, a2 + a5, a3 + a4, a3 + a5, a4 + a5} = {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.
Ограничения которые присутствуют в тестах:
посмотреть в олимпиаде
Два элемента массива ai, aj с индексами (i,j) 1≤i<j≤n, могут образовать пару и силой этой пары назовем ai+aj. Найдите силу пары, являющейся k-й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа n и k (1≤k≤n∗(n−1)2).Во второй строке через пробел заданы целые числа a1, a2, ..., an (0≤ai≤106).
Формат выходных данных:
Выведите ответ на задачу.Примеры:
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
Замечание:
В первом примере можно сделать три пары с силами {a1 + a2, a1 + a3, a2 + a3} = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.Во втором примере можно сделать десять пар с силами {a1 + a2, a1 + a3, a1 + a4, a1 + a5, a2 + a3, a2 + a4, a2 + a5, a3 + a4, a3 + a5, a4 + a5} = {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 балла.Ограничения которые присутствуют в тестах:
- 24 теста: 2≤n≤103
- 26 тестов: 2≤n≤104
Комментарий/решение:
=#include <bits/stdc++.h>
using namespace std;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n , k;
cin >> n >> k;
priority_queue<int>st;
vector<int>a(n);
for(int i = 0; i < n; ++i)cin >> a[i];
sort(a.begin() , a.end());
for(int i = 0; i < min(80000 , n); ++i){
for(int j = i + 1; j <= min(i + 350 , n - 1); ++j){
if(st.size() < k){
st.push(a[i] + a[j]);
}
else{
if(a[i] + a[j] < st.top()){
st.pop();
st.push(a[i] + a[j]);
}
}
}
}
cout << st.top();
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.