题意 给定n, k, 构造一个长度为n的序列，使得下面的式子的值最大，并且加起来小于等于k，最大能取到多少 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} |a[i] - a[j]|$ 注意到上面的式子跟序列的排列没有任何关系，每一位的贡献只需考虑有多少数大于或者小于等于它 然后我们假设构造一个非递减数列。 可以每次往一个后缀$+1$ 当往$i+1$的后缀$+1$时，对答案的贡献是 $i * (n - i)$ 即转化成了完全背包问题，用 $i * (n - i)$ 填满大小为 $k$ 的背包。 可以注意到k的值只有 $10^5$，猜一下 $i * (n - i)$ 小于等于 $10^5$ 的情况最多只有 $sqrt$ 个 可以通过 $i * (n - i) < 10^5$。 $i^2 - ni + 10^5 >= 0$ 向上的抛物线，当判定式小于0，即无交点时，全部i都满足重量小于等于10^5，此时 $n$ 是$\sqrt(400000)$ 判别式大于 $0$ 时有交点 超重的索引 $i$在两根之间，即 $sqrt(n^2 - 400000)$ 没超重的就是 $n - sqrt(n^2 - 400000)$ 注意在 $n+1$ 时，后者加的更多，所以恰好 $n$ 超过判别式时最大，取得两种情况的最大值只有 $600$ 多左右 $600 * 10^5$ 足够通过此题