rt，题意是一条数轴上 $n$ 个点分别在 $[1,n]$ 的位置，要求选出一个集合 $S=\{x|x\in[1,n]\}$，求 $min\sum_{i=2}^{n-1}\min\limits_{j\in S}(|i-j|)$。$n\leq 10^9$。

这东西（好像）明显是三分，但是不会，所以考场上打了个数论分块。当时不觉得是对的，但是 A 了。

具体就是枚举 $S$ 的大小，显然 $\forall i\in S$，使得 $|i-j|$ 对答案产生贡献的 $j$ 的数量要尽可能接近。发现 $\forall i$，$j$ 的数量为 $\frac ni$ 或 $\frac ni+1$，对这个数论分块，取每块两个端点更新答案。

求有没有严谨的证明。