题解：CF2254D Silhouette

chenqishuo · 2026-08-07 23:31:25 · 题解

题意简述

给定长度为 n 的数组 b，其中 b_i 表示原数组 a 中所有严格小于 a_i 的元素之和，即

要求构造一个字典序最小的正整数数组 a 满足上述条件，若不存在则输出 -1。

思路

设原数组 a 中不同的数值按照从小到大排序为 v_1 < v_2 < \dots < v_m，每个数值 v_k 的出现次数为 cnt_k。
对于某个数值 v_k，它的影子值（即 b 中对应位置的值）应该等于所有比它小的数值之和，即

其中 c_k 就是数值 v_k 对应的 b 值（且所有等于 v_k 的元素共享同一个 c_k）。

因此，我们先将给定的 b 排序并分组，得到一组不同的 b 值 c_1 < c_2 < \dots < c_m，以及每个值的出现次数 sz_1, sz_2, \dots, sz_m。
显然，最小的 b 值必须为 0（因为最小的 a 没有更小元素），否则无解。

• 若 m = 1，即所有 b_i = 0，则所有 a_i 可以相等，取最小值 1 即可。

• 否则，c_1 = 0。对于第一组（b=0），其 a 值记为 v_1。由于 c_2 是所有小于 v_2 的元素之和，而小于 v_2 的只有 v_1，所以

  c_2 = v_1 \cdot sz_1 \quad \Rightarrow \quad v_1 = \frac{c_2}{sz_1}

  必须整除且 v_1 > 0。

  一般地，对于 i = 2, 3, \dots, m-1，有

  c_{i+1} - c_i = v_i \cdot sz_i

  所以

  v_i = \frac{c_{i+1} - c_i}{sz_i}

  必须整除且满足 v_i > v_{i-1}。

  对于最后一组 c_m，它应该等于所有比它小的元素之和，即

  c_m = \sum_{p=1}^{m-1} v_p \cdot sz_p

  若该等式不成立则无解。同时，v_m 只需大于 v_{m-1}，可取 v_{m-1}+1（但 c_m 的等式已经包含了所有较小的元素，v_m 本身不影响影子值，所以可取最小合法值）。

若上述条件均满足，则每个位置 i 的 a_i 就是其 b_i 所对应的 v 值。因为 b 值相同的元素必须对应相同的 a 值（否则影子会不同），所以这样的构造是唯一的（或 m=1 时有多种但取最小），也就是字典序最小的。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;
int T, n, m, sz[N];
LL c[N], val[N];
pair<LL, int> b[N];
LL ans[N];

int main()
{
    scanf("%d", &T);
    while(T --)
    {
        bool flag = true;
        LL sum = 0;

        scanf("%d", &n);
        for(int i = 1;i <= n; ++ i)
        {
            scanf("%lld", &b[i].first);
            b[i].second = i;
        }

        sort(b + 1, b + n + 1);

        m = 0;
        for(int i = 1;i <= n; )
        {
            int j = i;
            while(j <= n && b[j].first == b[i].first) j ++;
            m ++;
            c[m] = b[i].first;
            sz[m] = j - i;
            i = j;
        }

        if(c[1] != 0) flag = false;

        if(flag && m == 1)
            val[1] = 1;
        else if(flag)
        {
            if((c[2] - c[1]) % sz[1] != 0) flag = false;
            else
            {
                val[1] = (c[2] - c[1]) / sz[1];
                if (val[1] <= 0) flag = false;
            }

            for(int i = 2; i < m && flag; ++ i)
            {
                if((c[i + 1] - c[i]) % sz[i] != 0) flag = false;
                else
                {
                    val[i] = (c[i + 1] - c[i]) / sz[i];
                    if (val[i] <= val[i - 1]) flag = false;
                }
            }

            if(flag)
            {
                val[m] = val[m - 1] + 1;
                for (int i = 1;i < m; ++ i)
                    sum += val[i] * sz[i];
                if (c[m] != sum) flag = false;
            }
        }

        if(!flag)
        {
            printf("-1\n");
            continue;
        }

        int j = 1;
        for (int i = 1;i <= n; ++ i)
        {
            while(j < m && b[i].first > c[j]) j ++;
            ans[b[i].second] = val[j];
        }

        for (int i = 1; i <= n; ++ i)
            printf("%lld%c", ans[i], i == n ? '\n' : ' ');
    }
    return 0;
}

在这里给个提醒，就是尽量使用 scanf 和 print，我赛时第一发用了关闭同步流被卡了。

原题通过记录