http://ru.wikipedia.org/wiki/Фибоначчиева_куча

IIRC ассимптотика проверки на принадлежность элемента O(1), вставка не помню, вроде то же что-то похожее.

Может быть входной массив отсортировать (один раз затратив O(n*log(n)) )

Сортировка массива из N небольших целых делается за O(N). Подробнее тут: http://en.wikipedia.org/wiki/Radix_sort

Нафейхоа сортировать, А?

нюбам засрали мозги контейнерами, классами и битовыми полями?? совсем отучились думать :(

решение в-лоб даёт O(n),

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int input[] = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4};
int N=sizeof(input)/sizeof(int);
int K = 10;
void print_pair(int *input,int K) {
        int *mem=alloca(sizeof(int)*K);
        int t,i;
        memset(mem,0,sizeof(int)*K);
        for(t=0;t<N;t++) {
                i=input[t];
                if (i<=0 || i>=K) continue;
                if (mem[K-i]!=0) {
                        printf("%d %d\n",i,K-i);
                        mem[K-i]=0;
                } else
                        mem[i]=1;
        }
}
int main() {
        print_pair(input,K);
        return 0;
}

с обычного С на то что называете С++, перевдёте сами

Идею одобряю, имплементация - говно.

вот кстати вариант без битсета, что лучше подойдет для варианта, где K большое, а входных чисел немного:

[code=cpp]#include <cstdio> #include <unordered_set> #include <vector>

using namespace std;

int main() { const int K = 10; unordered_set<int> s; vector<int> v = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4};

for( int n : v ) { if( s.find( K - n ) != s.end() ) printf( «%d %d\n», n, K - n ); s.insert( n ); } } [/code]

for( int n : v )

WTF is that‽

а если

{5,1,8,6,9,2,44,3,31,26,36,47,3,51,51,72,88,7,4};

хотя это лишь повторы.

WTF is that‽

C++11 АДИНАДИН

range-based for для плюсов

Если входные данные генерировать случайным образом (по всему диапазону указанного типа), то, очень вероятно, «решение в лоб» вывалится на переполнении стека (привет, alloca).

ТС как раз таки пытается рассуждать, а не бросается писать код. Логика нормальная для анализа сложности алгоритма. Сортируем за NLogN, далее линейно считаем пары, получаем NLogN. И уж потом можно отметить, что для маленьких натуральных чисел возможна линейная сортировка, и, соответственно линейный алгоритм поиска пар (что и отметил мэнхант). Такие дела.

Тред не читай, сразу отвечай

#include<iostream>

#define LEN(x) (sizeof(x)/sizeof(x[0]))
//const unsigned input[] = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4,5;
const unsigned input[] = {5,1,8,6,9,2,44,3,31,26,36,47,51,72,88,7,4,5,1000000-2};
//const unsigned input[] = {-10,20}; //where is my warning, mr GCC?
const unsigned K = 1000000;

int main()
{
	unsigned found[K+1] = {};
	for(const unsigned * i=input;i!=input+LEN(input);++i)
		if (*i<=K)
		{
			if (found[(K-*i)])
				std::cout << "(" << (K-*i) << " ," << *i << ")" << std::endl;
			found[*i]++;
		}
}

Вообще это конечно всё гонево, про O(n). это O1(n)+O2(K) и ещё не считая памяти. Для больших K придётся определять found как set или unordered_set (но во второй вставка дороже, емнип)

А где декремент found[*i] внутри if (found[(K-*i)]) ?

привет, alloca

alloca и прочие нестабильности исключительно от краткости (всё-таки тут форум а не git). Выдавать продакшн на вопрос а-ля 'лаба горит' - как то не феньково :)

ТС как раз таки пытается рассуждать

ТС мечется :) Явно нужно решение не для суперскаляров, а лекции и фривольная тех.литература ещё сказывается. Почти нащупал решение - но, блин, лучше посмотреть/спросить соседа по парте :)

и совсем P.S. давая подсказки по лабараторкам, принципиально прячу алгоритмические ошибки; НИКТО из высказавшихся их неувидил на фоне alloca :) rg-400 чё-то чуйкой почуял, но застеснялся что-ли :)

MKuznetsov, зачем обнулять mem[K-i] после if (mem[K-i]!=0)? Если на входе [3,5,5] то будет лишь одна пара.

при K=8

и совсем P.S. давая подсказки по лабараторкам, принципиально прячу алгоритмические ошибки; НИКТО из высказавшихся их неувидил на фоне alloca :) rg-400 чё-то чуйкой почуял, но застеснялся что-ли :)

Анонимов не читаешь?

А его специально нет. В условиях не сказано, может-ли одно число входить в разные пары. {5, 5, 5, 5} - это сколько пар?

Не говоря о том, что написанное тобой говно требует выделения 16 гигов на стеке (это в лучшем случае), ты как раз и реализовал вариант ОПа, завелосипедив кривой map с константным временем доступа.