ARC153C 题解

Galex · 2023-01-16 14:06:17 · 题解

考虑先随便构造满足要求的 x_1,x_2,\cdots,x_{n-1}，然后得到为了满足 \sum_{i=1}^n a_ix_i=0，x_n 的值。随后分类讨论。

为方便，钦定 a_n=1。若 a_n=-1，则将所有 a_i 变成 -a_i。

若 x_{n-1}<x_{n}，则说明此时是一组合法解，直接输出即可。

否则，若存在一个 p 满足 (\sum_{i=1}^p a_i)=1，则将 x_1,x_2,\cdots,x_p 都减去无穷大。这样 x_n 就需要加上无穷大，显然就能满足要求。

最后，若不存在这样的 p，则无解。证明比较显然。

一些实现上的细节：一开始 x_1,x_2,\cdots,x_{n-1} 可以设为 1,2,\cdots,n-1，无穷大设为差不多 10^{11} 就行。

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

int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9')
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}

int n;
int a[200005], ans[200005];

signed main() {
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    if (n == 1) {
        printf("Yes\n0");
        return 0;
    }
    if (a[n] == -1) {
        for (int i = 1; i <= n; i++)
            a[i] = -a[i];
    }
    int sum = 0;
    for (int i = 1; i < n; i++)
        ans[i] = i, sum += a[i] * i;
    ans[n] = -sum;
    if (ans[n] > ans[n - 1]) {
        printf("Yes\n");
        for (int i = 1; i <= n; i++)
            printf("%lld ", ans[i]);
        return 0;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += a[i];
        if (cnt > 0) {
            printf("Yes\n");
            for (int j = 1; j <= i; j++)
                ans[j] -= 300000000000;
            ans[n] += 300000000000;
            for (int j = 1; j <= n; j++)
                printf("%lld ", ans[j]);
            return 0;
        }
    }
    printf("No");
    return 0;
}