Question

Есть массив a состоящий из n целых чисел. Есть ли в массиве два различных индекса i и j такие, что ai + aj равна сумме всех остальных чисел массива?
Формат входных данных
В первой строке находится одно целое число n(3 6 n 6 105

) — размер массива.

Во второй строке находятся n целых чисел a1, a2, ..., an(1 6 ai 6 109

) — числа массива.

Формат выходных данных

Если есть два элемента массива, что их сумма равна сумме всех остальных элементов, то выве-
дите «YES». Иначе, выведите «NO».

Answer 1

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void solve(){

   int n, sum = 0;

   bool ok = false;

   cin >> n;

   vector<int> a(n);

   for(auto &i: a) { cin >> i; sum += i;}

   sort(a.begin(), a.end());

   for(int i = 0; i < n; i++){

       int l = i + 1, r = n - 1;

       while(l <= r && !ok){

           int m = (l + r) / 2;

           if(a[m] < sum - a[i])

               l = m + 1;

           else if(a[m] > sum - a[i])

               r = m - 1;

           else

               ok = true;

       }

   }

   cout << (ok ? "YES" : "NO");

}

int main(){

   solve();

}