Processing math: 100%

Областная олимпиада по информатике, 2018 год, 9 класс


(k-я пара) Вам задан массив a, состоящий из n целых чисел a1, a2, ..., an.
Два элемента массива ai, aj с индексами (i,j) 1i<jn, могут образовать пару и силой этой пары назовем ai+aj. Найдите силу пары, являющейся k-й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа n и k (1kn(n1)2).
Во второй строке через пробел заданы целые числа a1, a2, ..., an (0ai106).
Формат выходных данных:
Выведите ответ на задачу.
Примеры:
1.Вход:
3 3
7 1 4
Ответ:
11
2.Вход:
5 7
1 5 3 5 3
Ответ:
8
3.Вход:
10 32
0 0 0 0 0 0 0 0 0 0
Ответ:
0
4.Вход:
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 балла.
Ограничения которые присутствуют в тестах:
( Yeskendir Sultanov )
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   -2
5 года 2 месяца назад #

показать/скрыть код

C++

пред. Правка 2   -1
4 года 1 месяца назад #

[deleted.]

пред. Правка 2   1
6 года 2 месяца назад #

  0
5 года 4 месяца назад #

//TLE 26 test

показать/скрыть код

C++

  0
5 года 4 месяца назад #

попробуйте использовать scanf и не используйте vector а простой массив

пред. Правка 5   0
4 года 1 месяца назад #

[deleted.]

пред. Правка 3   -1
4 года 1 месяца назад #

[deleted.]

пред. Правка 3   0
4 года 1 месяца назад #

[deleted.]

  0
5 года 2 месяца назад #

Нет такое решение не пройдет.

Полное решение предполагает использование бинпоиска по ответу.

Отсортируем числа. Для конкретной суммы C посчитаем сколько таких, что ai+aj<C. это делается за линию.

Если переберем С бинпоиском получим асимптотику  Nlog(max(2ai))

пред. Правка 2   0
4 года 1 месяца назад #

[deleted.]

  0
5 года 2 месяца назад #

показать/скрыть код

C++

  0
3 года 2 месяца назад #

показать/скрыть код

C++

  0
3 года назад #

На питоне

показать/скрыть код

C++

  0
1 месяца 28 дней назад #

=#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();

}показать/скрыть код

C++