首页 > 其他分享 >CF1852B Imbalanced Arrays 题解

CF1852B Imbalanced Arrays 题解

时间:2023-09-16 10:37:16浏览次数:47  
标签:int 题解 void Arrays read 绝对值 数组 Imbalanced

CF1852B Imbalanced Arrays 题解

洛谷

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;
}

标签:int,题解,void,Arrays,read,绝对值,数组,Imbalanced
From: https://www.cnblogs.com/yuhang-ren/p/solution-CF1852.html

相关文章

  • LeetCode-Java题解 209. Minimum Size Subarray Sum
    题目地址:209.MinimumSizeSubarraySum解题思路:    看到这道题,心里本身是有双指针这个概念的,但是不知道怎么用,脑子里第一反应就是暴力解法,双for一把梭,然后时间就超时了...看了题解才知道滑动窗口这个解法,不禁直呼妙啊!感觉和双指针非常类似,其核心点在于避免了暴力算法的枚......
  • 题解 UVA1566 John
    题目描述两个人轮流取石子,每人每次可以\([1,a_i]\)个石子,最后取完石子的人为负。问最终谁会赢。具体思路若堆数为\(1\)且该堆数量为\(1\),先手必败。若堆数不为\(1\)且每堆数量都为\(1\),若有奇数堆,先手比败,否则,先手必胜。若堆数不为\(1\),转换为\(Nim\)游戏,判......
  • 洛谷题解 | P1046 陶陶摘苹果
    ​目录题目描述输入格式输出格式输入输出样例说明/提示题目思路AC代码题目描述陶陶家的院子里有一棵苹果树,每到秋天树上就会结出 10个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个 30厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。现......
  • 《特殊函数概论》Chapter 3习题解答
    《特殊函数概论》Chapter3习题解答卷心汪汪队众所周知,王竹溪、郭敦仁所著的《特殊函数概论》是一本对初学特殊函数的同学非常友好的书,特别是对我这种英语不好的人来讲,不用一边翻字典一边看Whittaker&Waston了但是据我所知,特殊函数概论应该是没有完整......
  • 题解 P8920 『MdOI R5』Variance
    题目描述给你两个长度为\(n\)的序列\(a\)和\(b\),让你选\(n\)个\(c_i\in[a_i,b_i]\),使得\(\frac{1}{n}\sum_{i=1}^n(c_i-\overlinec)^2\)最大。具体思路首先我们从方差的定义出发,方差代表了数据的波动程度,公式为:$$s^2=\frac{1}{n}\sum_{i=1}^n(a_i-\overline......
  • Fox and Minimal path 题解
    FoxandMinimalpath题目大意构造一张无向图,使得从\(1\)到\(2\)的最短路数量为\(k\)。思路分析我们首先可以发现当\(k=2^t\)时的构造方式:其中只有\(O(\logk)\)个点。当\(k\not=2^t\)时,我们可以将\(k\)二进制拆分,对于每一个二进制位重复上述操作,就可以得......
  • 课堂问题解答
    一、运行结果:由于浮点数在计算机内部的表示方式是有限的,所以在进行浮点数计算时可能会出现精度损失,导致结果不是准确的。在第一行代码中,计算0.05+0.01的结果,预期应该是0.06。然而,由于浮点数的精度限制,实际计算结果可能是一个近似值,例如0.060000000000000005。这就导致了打......
  • NOI 2023 题解
    CopperLoser的题解……Day1T1方格染色有一个\(n\timesm\)的网格,有\(Q\)次操作,每次形如有三种:将\((x_i+j,y_i)\)/\((x_i,y_i+j)\)/\((x_i+j,y_i+j)\)染色,其中\(j=0,1\dotsL_i-1\)。第三种操作至多只有\(5\)次,问之中有多少个格子被染过色。扫描线板子题,首先令......
  • 『题解』P6055
    给出\(N\),求:\[\sum_{i=1}^N\sum_{j=1}^N\sum_{p=1}^{\lfloor\frac{N}{j}\rfloor}\sum_{q=1}^{\lfloor\frac{N}{j}\rfloor}[\gcd(i,j)=1][\gcd(p,q)=1].\]考虑化简。存在一个性质,但是我当时推的时候忘记了。即:\[\sum_{i=1}^N\sum_{j=1}^N\su......
  • 9.11CF1819 题解
    9.11CF1819题解A.ConstructiveProblem简单题,上链接:链接B.TheButcher题意有一张 \(h\timesw\) 的纸片,现在对这张纸片进行 \(n−1\) 次裁剪。每次裁剪后会将其中一半收归(即这一半不会再被裁剪)。保证纸片不会被旋转。告诉你最终裁剪后的 \(n\) 张纸片长宽,问初始......