CF1852A Ntarsis' Set 题解

link T1 desu

$1\leq n \leq 10^5,1\leq k\leq 10^9,1\leq a_i \leq 10^9$

显然只需要讨论 $a_1=1$ 的情况。

令答案为 $p$。

正着做发现复杂度很难不与 $a_n$ 或 $k$ 有关联。那么考虑倒着做。

显然有结论：第 $i$ 轮之后留下的数都是没有在第 $i$ 轮被删除的。

那么我们考虑最后一轮 $p$ 在 $S$ 中第 $x=1$ 位。找到上一轮的第 $x$ 个空位置，成为下一轮新的位置。

比如有 a= 1 3 5 7，$p$ 的位置变化：1 -> 2 -> 4 -> 8 -> 12 -> 16。

观察发现，找到空位置的过程并成为下一个空位置，实际上是在 $a$ 中找到第 $x$ 个空位置前有多少个填充的位置并 $x\leftarrow x+fill$。

比如 6 是第 $3$ 个空位置，那么 $x'=3+3$。

由于 $x$ 不断增大，可以使用一个指针来指向第 $x$ 个空位置前的填充位置来计算 $fill$。

然后当 $x$ 足够大时，$fill=n$。

那么就可以直接加速了。

代码

ll now=1;
void solve(){
	int j=0,t;
	for(t=k;t>=1;--t){
		while(j<=n&&a[j]-j<now) ++j;
		now=now+(j-1);
		if(j-1==n) break;
	}
	if(t>=1) now+=n*1ll*(t-1);
	printf("%lld\n",now);
}