CF1852B Imbalanced Arrays 题解
Links
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