#include <iostream>
#include <vector>
using namespace std;
// глобальные переменные
const int arraySize = 10;
vector <int> numbers;
// сам алгоритм.
void result(){
// совет - обьявляй все переменные в начале функции
int leader = 0;
int maxCount = 0;
int count = 0;
// поиск самого частого числа
for (int c = 0; c < 9;c++){
// обнуляем счетчик
count = 0;
for (int c1 = 0;c1 < arraySize;c1++){
if (numbers[c1] == c) count++;
}
// проверка на лидера
if (maxCount < count){
leader = c;
maxCount = count;
}
}
// ну..с посмотрим:
cout << "Leader: " << leader << " (" << maxCount << ") " << std::endl;
}
int main()
{
// подготовка масива
srand(time(NULL)); // обнулем внутрений таймер для полного рандома
for (int c = 0; c < arraySize;c++) {
numbers.push_back(rand() % 9); // заполняем масив числами
}
// посмотрим на оригинальный масив
cout << "Original array: ";
for (int c = 0;c < arraySize;c++) cout << numbers[c] << " ";
cout << std::endl;
// сортировка
result();
return 0;
}
Объяснение:
Хорошая книга по с++: Герберт Шилд - с++ базовый курс.
Пусть сумма всех элементов равна full_sum, а длина массива 2k.
Предлагаю организовать банальный перебор: выберем k индексов из 2k, посчитаем сумму соответствующих элементов. Будем искать максимальную сумму, которая не превосходит full_sum/2. При этом сумма невыбранных элементов будет не меньше full_sum/2, и будет отличаться от суммы выбранных элементов на минимально возможную величину.
Этот алгоритм работает быстро только для относительно небольших значений k. если нужно что-то быстрее, то придется придумывать что-то дополнительно.
Код (Python 3):
from random import randint
from itertools import combinations
k = 10
a = [randint(1, 100) for _ in range(2 * k)]
print(*a)
full_sum = sum(a)
half_sum = full_sum // 2
max_sum = -1
answer = None
for seq in combinations(range(2 * k), k):
s = sum(map(lambda ind: a[ind], seq))
if s <= half_sum and s > max_sum:
max_sum, answer = s, seq
if s == half_sum:
break
left = [a[i] for i in answer]
right = [el for i, el in enumerate(a) if i not in answer]
a = left + right
print(*a)
Пример вывода:
50 39 19 63 16 4 82 45 63 33 6 57 39 16 38 4 66 56 87 84
50 39 19 63 16 4 82 57 16 87 45 63 33 6 39 38 4 66 56 84