https://codeforces.com/contest/808/problem/D
题目大意
给出 $n \ (n \le 10^5)$ 长的数组，其中元素 $1 \le a_i \le 10^9$ 问是否可以将其中某任意元素移动到其他任意位置，之后使得数组可以分成左右和相等的两部分。
简要题解
因为不增删数字，所以如果整个数组和为奇数无解。否则最后分成的最右两半，和是数组和的一半，记为 $Tar$。如果数组中存在 $Tar$ 则显然将其移动到开头或者结尾即可。 否则我们考虑最终分界的位置，则我们需要将某元素从分解左侧移出，或从分界右侧移入，我们根据前缀和和 $Tar$ 计算出元素的值，并查询其在左右是否存在即可。
注意这题都是正数，但其实有 $0$ 和负数也可以一样做。
特别的，因为和会溢出 int 如果使用 multiset
复杂度
$T$：$O(n log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int INF = 0x3f3f3f3f;
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
LL sum = 0;
for (int i : a) {
sum += i;
}
if (sum & 1) {
cout << "NO\n";
return;
}
multiset<int> lse, rse;
for (int i : a) {
rse.insert(i);
}
sum /= 2;
if (rse.count(sum)) {
cout << "YES\n";
return;
}
LL cur = 0;
for (int i : a) {
cur += i;
lse.insert(i);
rse.erase(rse.find(i));
if (cur < sum) {
if (sum - cur < INF && rse.count(sum - cur)) {
cout << "YES\n";
return;
}
} else {
if (cur - sum < INF && lse.count(cur - sum)) {
cout << "YES\n";
return;
}
}
}
cout << "NO\n";
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] E. Selling Souvenirs - Educational Codeforces Round 21