Простая задача с архива


Информатики дорогие, помогите пожалуйста с задачей, что то никак не могу решить, в общем суть задачи найти минимальное число, которое нельзя представить в виде суммы нескольких (возможно одного) элементов массива.
P.S. ссылка на задание:
Sort Me (no ad)

1 симпатия

Первое, что приходит в голову это то, что любое число, которое можно собрать в такой системе исчисления - сумма разных элементов массива а. Мы точно не сможем собрать число sum(a) + 1.

Заметим, что то, в каком порядке мы будем использовать разряды не имеет никакого значения. Тогда, можно представить разряды в порядке неубывания. Отсортируем массив.

Заведем переменную сur_sum, которая будет суммой элементов от 0 до i. Изначально, она инициализрована с значением 0. Для каждого i надо проверить, что a[i] - 1 меньше или равно cur_sum для i - 1 (в случае i = 0, просто сравниваем a[0] - 1 с нулем). Если условие выполнено, то мы можем собрать любые натуральные значения от 1 до cur_sum + a[i]. Обновляем: cur_sum += a[i]. Иначе, при невыполнении условия, ответом будет cur_sum + 1.

Почему, если условие выполняется, мы можем собрать любое число от 1 до сur_sum + a[i]?
Скажем, что мы точно можем собрать все числа от 1 до cur_sum. Тогда, нужно проверить, можем ли мы собрать числа на отрезке от cur_sum + 1 до cur_sum + a[i]. Очевидно, мы можем собрать cur_sum + a[i] - 1, просто не взяв в сумму единицу. То же самое работает с cur_sum + a[i] - 2. Тогда, чтобы собрать cur_sum + 1, можно использовать cur_sum + a[i] - (a[i] - 1). Такое возможно, если мы уже умеем собирать число a[i] - 1. Чтобы это проверить, достаточно сравнить cur_sum и a[i] - 1.

Не суперски объяснил на самом деле, может кто сможет донести идею понятней.

#define ll long long
int main() {
	int n; cin >> n;
	ll a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	ll cur_sum = 0;
	for (int i = 0; i < n; i++) {
		if (cur_sum < a[i] - 1) {
			break;
		}
		cur_sum += a[i];
	}
	cout << cur_sum + 1;
}
7 симпатий

image
Спасибо!