士兵

发布时间 2023-12-07 17:33:41作者: 最爱丁珰

这题每一步操作都合法的正确性还是要深刻理解七夕祭之后再来证,不太清楚。。

说一下\(x\)怎么搞

首先有一个显而易见的,对于一个坐标轴上的分布在各个点的许多人,如果要他们进行移动最后相邻,那么最后这个队列中,他们的相对顺序不变。比如说最开始\(x\)从大到小为1号,2号,3号,那么最终队列1号后面一定是2号,2号后面一定是3号。不然的话交换两人的目的地答案不会变差(分多种情况讨论即可)

所以对这一道题目,假设最终队列中第一个人的位置是\(pos\),那么答案就是\(\sum_{i=1}^{n}|x_i-(pos+i)|\)(下标从0开始)

所以对\(x\)排序后,减去\(i\)即可用中位数做