算法
(暴力枚举) $O(n)$
先求出所有元素之和 $s$,然后枚举每个非零元素找出对哪个元素进行操作是最佳的。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
using ll = long long;
const ll LINF = 1001002003004005006ll;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
// ll s = 0;
// rep(i, n) s += a[i];
ll s = std::accumulate(a.begin(), a.end(), 0ll);
ll ans = LINF;
if (s % 2 == 0 and s >= 0) ans = s;
rep(i, n) {
a[i] = std::abs(a[i]);
if (a[i]) {
ll r = s % a[i];
if (r % 2 == 0)
ans = min(ans, r);
else {
if (a[i] % 2 == 1)
ans = min(ans, r + a[i]);
}
}
}
cout << (ans == LINF ? -1 : ans) << '\n';
return 0;
}