Codeforces-Round-#812C题解

Codeforces Round #812 C. Build Permutation

题目大意

一个满足如下规则的从零开始标号数列a可以称之为好：

$\forall i \in [0,n), a_i + i = y^2, y\in\mathbb{Z}$

给定数字$n$, 求出排列$[0,1,2 \dots n-1]$的排列$p$,使得$p$为一个好的数列

有T组数据

数据规模

$1\leq T\leq 10^4$

$1\leq n \leq 10^5$

$\Sigma n \leq 10^5$

我的思路(无)

大佬代码

jiangly

对于$n-1$，查找大于等于$n-1$的最小的完全平方数$v$,并将其与$v-n+1$相匹配，即:

for (int i = v - r + 1; i < r; i++)
{
	p[i] = v - i;
}

接着将n迭代为$v-n+1$,重复操作，直到n=0

时间复杂度:$\Theta(n)$