Решение задачи Хороший массив с Codeforces

Без пояснения   Просмотров: 1835

Назовем массив хорошим, если в нем есть элемент, равный сумме всех остальных элементов. Например, массив a=[1,3,3,7] — хороший, так как a4=7 равно 1+3+3.

Вам дан массив a из n целых чисел. Ваше задание — найти все такие индексы j этого массива, что после удаления j-го элемента массив станет хорошим (назовем такие индексы красивыми).

Например, если a=[8,3,5,2], красивые индексы — 1 и 4:

при удалении a1 массив станет [3,5,2], и этот массив хороший;
при удалении a4 массив станет [8,3,5], и этот массив хороший.
Все удаления надо рассматривать независимо, то есть для каждого индекса надо удалить элемент, проверить, что массив теперь хороший, и после этого вставить элемент обратно.

Код 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,sum;
ll a[200009];
ll b[200009];
vector<ll>ans;
int main(){
	cin>>n;
	for(int i = 0; i < n; i++)
        cin >> a[i], b[i] = a[i], sum += a[i];
	sort(b, b + n);
	for(int i = 0; i < n; i++){
		ll mx = b[n - 1];
		if(b[n - 1] == a[i])
            mx = b[n - 2];
		if(sum - (a[i] + mx) == mx)
            ans.push_back(i + 1);
	}
	cout << ans.size() << endl;
	for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
	cout << endl;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp