出处： Codeforces Round 887
链接： https://codeforces.com/problemset/problem/1852/B
题目大意：
给定一个包含 \(n\) 个非负整数的频次序列 \(f\) 。
构造任意一个等长的整数序列 \(b\) ，要求
① \(b \in [-n, n]\) but $b \neq 0 $
② \(b\) 中不存在相反数
③ 对于每个坐标 \(i\) ，序列中的（可以和 \(i\) 重复的）坐标 \(j\) ，且能满足 \(b_i+b_j>0\) 的 \(j\) 的个数刚好为 \(f_i\) 频次
说明不存在这样的 \(b\) 满足这个条件。
约束： \(1\leq n \leq 10^5\) ， \(0\leq f_i \leq 10^5\) 。
解题思路：
-
先观察有什么规律
构造 \(b\) 序列时的前两个要求，其实变相说明了只能从 \(\{-n,n\}, \{-n+1, n-1\}, \dots, \{-1, 1\}\) 里面每组挑选至多一个作为值出现。
引理1：假设要选出 \(6\) 个不同的值，则选出的值必定满足以下两种模式其中之一：① \(-6,-4,-2,1,3,5\) 或者 \(-5,-3,-1,2,4,6\) 。证明似乎是显然的，因为构造 \(b\) 序列时的前两个要求导致的。
引理2：假如要选出 \(n\) 个值，并且运行一部分的值重复，得到的序列依然满足上一条引理约束的模式。也就是对于 \(0\) 的同一侧，距离必定相差为 \(2\) ，且 \(0\) 的两侧的奇偶值必定相反，且一定从 \(-2,-1,1,2\) 这样的值开始。首先先证明为什么距离必定是 \(2\) ，因为假如距离大于 \(2\) 则中间可以插入另一个相反数，而几个连续的相反数之间对于是否和对侧的相反数加起来超过 \(0\) 是没有变化的，也就是说他们是等价的。比如对于 \(-6,-2\) 来说， \(3,4,5\) 其实是完全等价的。没有意义，可以约简为 \(3\) ，进而把 \(-6\) 约简为 \(-4\) ，转换成上一条引理约束的形式。
引理3：越大的频次，对应的 \(b\) 值应该越大。这是一个显然的单调性。
引理4：相同的频次，对应相同的 \(b\) 值。这个没有那么明显，但用反证法去看也是一样的。如果某个相同的频次 \(f\) 对应的 \(b\) 值不同，那么这两个 \(b\) 值中间不能插入其他的相反数，否则会导致频次至少相差 \(1\) ，矛盾。
引理5：相同的 \(b\) 值，对应相同的频次。这个很明显，因为 \(b\) 序列确定了之后，是跟位置完全无关的，所以一定会得到相同的频次。
根据上面的引理，可以知道一个约简的办法，就是先数一数有多少种不同的频次，记为 \(cntF\) 种，那么只需要验证引理1中的两个模式的 \(b\) 序列即可知道是否有解，其他的模式一定完全等价于这两个模式。并且由于引理3和引理4，可以知道每一个 \(b\) 值是和某一个频次唯一一一对应的。
-
算法和复杂度细节
既然知道了构造的方法是唯一（唯二？）的，那么只需要编程就行了。
由于引理3，所以要对频次进行一个排序（同时要保留原本输入的顺序用以输出，可以用常见的
pair<int, int>和sort搞定。），排序之后就可以贪心去给每个频次分配一个 \(b\) 值。复杂度为 \(O(nlogn)\) 。构造出 \(b\) 序列之后，在验证频次是否合理的过程中，也可以使用双指针等方法进行加速，实在偷懒可以用一个树状数组啥的。复杂度为 \(O(n)\) 。
构造出第一个 \(b\) 序列之后，再构造另一个重新计算一次，注意这里要特别处理经过 \(0\) 的情况。
点击查看代码
int n;
pii f[200005];
int b[200005];
int sortB[200005];
bool check (int cntF) {
if (cntF == 0) {
// 非常重要，要避开 0 ！！！
--cntF;
}
int curB = cntF;
for (int i = 1; i <= n; ++i) {
if (i > 1 && f[i].first != f[i - 1].first) {
// b 序列中， 0 的同一侧，相邻的值差为 2
curB -= 2;
if (curB == 0 || curB == -1) {
// 如果 -2 之后越过了0，说明之前是 2 或者 1，这里要避开 0 或者 -1
--curB;
}
}
b[f[i].second] = curB;
sortB[i] = curB;
}
int r = n; // 用双指针法计算 b[i] + b[j] > 0 的频次
for (int i = 1; i <= n; ++i) {
while (r > 0 && sortB[r] + sortB[i] <= 0) {
--r;
}
// sortB[r] + sort[i] > 0
if (f[i].first != r) {
return false;
}
}
return true;
}
void solve() {
RD (n);
for (int i = 1; i <= n; ++i) {
RD (f[i].first);
f[i].second = i;
}
sort (f + 1, f + 1 + n);
reverse (f + 1, f + 1 + n); // 套引理3，从大到小进行构造
int cntF = 0;
for (int i = 1; i <= n; ++i) {
if (i == 1 || f[i].first != f[i - 1].first) {
++cntF; // 计算一共有多少种不同的频次，用于套引理1进行构造
}
}
if (check (cntF) || check (cntF - 1)) {
// 对于偶数：
// 6, 4, 2, -1, -3, -5
// 5, 3, 1, -2, -4, -6
// 对于奇数：
// 7, 5, 3, 1, -2, -4, -6
// 6, 4, 2, -1, -3, -5, -7
puts ("YES");
WTN (b, n);
} else {
puts ("NO");
}
}
- 用此算法计算出的 \(b\) 是绝对值之和最小的 \(b\) ，与官方题解的答案略有不同。