题解 | A. 爆零什么的千万不要啊

A. 爆零什么的千万不要啊

总链接：https://blog.nowcoder.net/n/621ba39d00774b9c89afbe3c1e8935fa

本场比赛最难的题，属于构造题

构造题的证明往往比较复杂，需要投机取巧

但是本题不经过严谨证明很难 AC，所以还是老老实实证明吧

首先手玩一会找特殊情况， 是比较特殊的

当不为零的数字少于 时，我们的两个端点必定出现 ，无解

反之 直接往中间塞就行，没有影响，此时只需要考虑非零数

对于非零数，如果全为正或者全为负，必定有解

反之正，负都同时存在，此时如果总和 ，必定无解

反之我们不妨令 ，此时将正负分到两边

正数加完再加入负数的过程中，我们的 不会经过 ，很安全

而负数加完再加正数的过程中，我们的 会从负数变为正数，中间有可能经过

下面思考什么时候会经过 ，以及如何避免

假设负数加完的总和为 ，当正数种类不唯一的时候，如果某个方案 会使得 ，我们可以通过交换 中某个数为其他种类数来避免取

如果换入的数更大，直接跨越了 ，有解

如果换入的小，由于该数是一个正数，再放入 后也会跨越 ，有解

当正数种类唯一呢？假设全取 ，此时如果 ，其中 为负数集合的某个元素，只需要挪动 到开头就能保证后续不取

反之负数全是 的倍数，且正数全为 ，到这一步就好做了

由于最终的 ，如果 在某个时刻为负数，后续一定会恰好经过

因此 必须时刻保持 的状态，我们必须有足够多的 ，从而无论正向还是反向都可保持

推导一下就能发现合法条件为 ，即

代码如下

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

const char YES[] = "Accepted\n";
const char NO[] = "gg\n";

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;
    assert(1 <= n && n <= 1000000);

    vector<ll> a(n + 1);
    foreach (i, 1, n)
        cin >> a[i], assert(-1000000000 <= a[i] && a[i] <= 1000000000);

    if (n == 1)
    {
        cout << (a[1] ? YES : NO);
        return 0;
    }

    int nzc = 0;
    foreach (i, 1, n)
        nzc += a[i] != 0;

    if (nzc < 2)
    {
        cout << NO;
        return 0;
    }

    vector<ll> pt, nt;
    pt.reserve(n);
    nt.reserve(n);

    ll psum = 0, nsum = 0;
    foreach (i, 1, n)
    {
        if (a[i])
        {
            if (a[i] > 0)
                pt.emplace_back(a[i]), psum += a[i];
            else
                nt.emplace_back(-a[i]), nsum += -a[i];
        }
    }

    if (psum == nsum)
    {
        cout << NO;
        return 0;
    }

    if (psum < nsum)
    {
        swap(psum, nsum);
        swap(pt, nt);
    }

    if (!nsum)
    {
        cout << YES;
        return 0;
    }

    if (pt.front() == pt.back())
    {
        for (auto v : nt)
        {
            if (v % pt.front())
            {
                cout << YES;
                return 0;
            }
        }

        // 5 5 -5 5 5
        if (psum - nsum > pt.front() + *std::max_element(nt.begin(), nt.end()))
        {
            cout << YES;
            return 0;
        }
    }
    else
    {
        cout << YES;
        return 0;
    }

    cout << NO;
    return 0;
}

扩展思考：无