CF1852B Imbalanced Arrays 题解

Links

洛谷

Codeforces

Description

对于一个给定的长度为 \(n\) 的数组 \(A\)，定义一个长度为 \(n\) 的数组 \(B\) 是不平衡的当且仅当以下全部条件满足：

• \(-n \leq B_{i} \leq n\) 且 \(B_{i} \ne 0\)。即每个数在 \([-n,n]\) 内且不为 \(0\)。

• \(\forall i,j \in [1,n], B_{i} + B_{j} \neq 0\)。即数组内不存在一对相反数。

• \(\forall i \in [1,n], \sum_{j = 1}^{n} [ \left (B_{i} + B_{j} \right) > 0] = A_{i}\)。即对于任意的 \(i\)，数组中与 \(B_{i}\) 和大于 \(0\) 的数的个数恰好为 \(A_{i}\)。注意：这里需要计算本身。也即 \(i\) 与 \(j\) 可以相等。

请构造长度为 \(n\) 的不平衡序列。

多组测试数据。

Solution

手模了一下数据。发现绝对值最大的数很有意义。假设这个数下标为 \(k\)，继续研究可以发现，若这个数大于 \(0\)，则它与所有数相加都大于 \(0\)，此时 \(a_{k}\) 为 \(n\)，否则它与所有数相加都小于 \(0\)，此时 \(a_{k}\) 为 \(0\)。由于绝对值最大的数要么是正数，要么是负数（题目中说了没有 \(0\)），因此以上两个必定满足一个，否则无解。

按照上面的思路，我们只能求出一个数，如何才能把这个思路延续下去呢，我们发现可以不考虑这个数，将序列的长度减 \(1\)，若绝对值最大的数为正数，我们还需要将 \(a\) 数组的每个数减 \(1\) 来排除这个数的贡献。

于是每个数就都可以根据序列能剩余数的数量确定。

如果上面没看懂就来看一下实现吧，首先方便找最大数和 \(0\)，将 \(a\) 从大到小排序，注意要记录原来的位置。

read(n);
for(int i = 1;i <= n;i++)
{
    read(nums[i].first);
    nums[i].second = i;
}
sort(nums + 1,nums + n + 1);
reverse(nums + 1,nums + n + 1);

接下来开始枚举。用 det 记录整个序列被减去的值。

判断两种无解的情况，并计算当前数的答案。由于每次都会减少一个数，因此数组中的数绝对值互不相同，满足了第一个条件。

int tail = n,det = 0;
for(int i = 1;i <= tail;i++)
{
    if(nums[i].first - det == tail - i + 1 && nums[tail].first - det <= 0)
    {
        puts("NO");
        return ;
    }
    if(nums[i].first - det != tail - i + 1 && nums[tail].first - det != 0)
    {
        puts("NO");
        return ;
    }
    if(nums[i].first - det == tail - i + 1)
    {
        ans[nums[i].second] = tail - i + 1;
        ++det;
    }
    else
    {
        ans[nums[tail].second] = -(tail - i + 1);
        --tail;
        --i;
    }
}

Codes

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 520011
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return ;
}
void write_(int x)
{
    if(x < 0)
    {
        putchar('-');

        x = -x;
    }
    if(x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    puts("");
}
int T;
int n;
pair<int,int> nums[max_n];
int ans[max_n];
void solution()
{
    read(n);
    for(int i = 1;i <= n;i++)
    {
        read(nums[i].first);
        nums[i].second = i;
    }
    sort(nums + 1,nums + n + 1);
    reverse(nums + 1,nums + n + 1);
    int tail = n,det = 0;
    for(int i = 1;i <= tail;i++)
    {
        if(nums[i].first - det == tail - i + 1 && nums[tail].first - det <= 0)
        {
            puts("NO");
            return ;
        }
        if(nums[i].first - det != tail - i + 1 && nums[tail].first - det != 0)
        {
            puts("NO");
            return ;
        }
        if(nums[i].first - det == tail - i + 1)
        {
            ans[nums[i].second] = tail - i + 1;
            ++det;
        }
        else
        {
            ans[nums[tail].second] = -(tail - i + 1);
            --tail;
            --i;
        }
    }
    puts("YES");
    for(int i = 1;i <= n;i++)
    {
        writesp(ans[i]);
    }
    puts("");
}
signed main()
{
    read(T);
    while(T--)
    {
        solution();
    }
    return 0;
}