【POJ 1723】SOLDIERS（排序、中位数）

题面：SOLDIERS

题目大意

有 $n$ 个士兵，并且知道每个士兵在二维坐标图上的位置。

士兵可以进行移动，但是每个士兵每次只能向上、向下、向左或向右移动一个单位，因此，他的 $x$ 或 $y$ 坐标也将相应的加 1 或减 1。

现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的y坐标相同并且x坐标相邻。

请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。

注意：两个或多个士兵不能占据同一个位置。

思路

分析题目，可以发现，每个士兵的横纵坐标对于他们的移动是彼此独立的，即一个士兵可以先移动好 $x$ 坐标再移动 $y$ 坐标，也可以先移动好 $y$ 坐标再移动 $x$ 坐标，或者可以交叉移动。

此时，我第一时间想到的就是货仓选址问题一样的做法，即排序找中位数求各个点到中点的距离之和的最小值。也容易发现，由于 $y$ 要统一（即所有士兵最终的 $y$ 坐标是一致的），所以在 $y$ 轴上是可以这样做的。

但是 $x$ 轴是按单位 1 递增排序的。所以需要稍微变形一下。

我们先试一下给 $x$ 先排好序。

当 $x$ 已经排好序之后，由于最终的 $x$ 序列是一个公差为 1 的等差数列 $a$，所以排好序的 $x$ 序列和最终要形成的序列其实是一一对应的，即：

#mermaid-svg-IELxa0wXsqqEv6FT .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-IELxa0wXsqqEv6FT .label text{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .node rect,#mermaid-svg-IELxa0wXsqqEv6FT .node circle,#mermaid-svg-IELxa0wXsqqEv6FT .node ellipse,#mermaid-svg-IELxa0wXsqqEv6FT .node polygon,#mermaid-svg-IELxa0wXsqqEv6FT .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-IELxa0wXsqqEv6FT .node .label{text-align:center;fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .node.clickable{cursor:pointer}#mermaid-svg-IELxa0wXsqqEv6FT .arrowheadPath{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-IELxa0wXsqqEv6FT .flowchart-link{stroke:#333;fill:none}#mermaid-svg-IELxa0wXsqqEv6FT .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-IELxa0wXsqqEv6FT .edgeLabel rect{opacity:0.9}#mermaid-svg-IELxa0wXsqqEv6FT .edgeLabel span{color:#333}#mermaid-svg-IELxa0wXsqqEv6FT .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-IELxa0wXsqqEv6FT .cluster text{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-IELxa0wXsqqEv6FT .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-IELxa0wXsqqEv6FT text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-IELxa0wXsqqEv6FT .actor-line{stroke:grey}#mermaid-svg-IELxa0wXsqqEv6FT .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-IELxa0wXsqqEv6FT .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-IELxa0wXsqqEv6FT #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-IELxa0wXsqqEv6FT .sequenceNumber{fill:#fff}#mermaid-svg-IELxa0wXsqqEv6FT #sequencenumber{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT #crosshead path{fill:#333;stroke:#333}#mermaid-svg-IELxa0wXsqqEv6FT .messageText{fill:#333;stroke:#333}#mermaid-svg-IELxa0wXsqqEv6FT .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-IELxa0wXsqqEv6FT .labelText,#mermaid-svg-IELxa0wXsqqEv6FT .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-IELxa0wXsqqEv6FT .loopText,#mermaid-svg-IELxa0wXsqqEv6FT .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-IELxa0wXsqqEv6FT .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-IELxa0wXsqqEv6FT .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-IELxa0wXsqqEv6FT .noteText,#mermaid-svg-IELxa0wXsqqEv6FT .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-IELxa0wXsqqEv6FT .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-IELxa0wXsqqEv6FT .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-IELxa0wXsqqEv6FT .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-IELxa0wXsqqEv6FT .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .section{stroke:none;opacity:0.2}#mermaid-svg-IELxa0wXsqqEv6FT .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-IELxa0wXsqqEv6FT .section2{fill:#fff400}#mermaid-svg-IELxa0wXsqqEv6FT .section1,#mermaid-svg-IELxa0wXsqqEv6FT .section3{fill:#fff;opacity:0.2}#mermaid-svg-IELxa0wXsqqEv6FT .sectionTitle0{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .sectionTitle1{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .sectionTitle2{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .sectionTitle3{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-IELxa0wXsqqEv6FT .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .grid path{stroke-width:0}#mermaid-svg-IELxa0wXsqqEv6FT .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-IELxa0wXsqqEv6FT .task{stroke-width:2}#mermaid-svg-IELxa0wXsqqEv6FT .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .taskText:not([font-size]){font-size:11px}#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-IELxa0wXsqqEv6FT .task.clickable{cursor:pointer}#mermaid-svg-IELxa0wXsqqEv6FT .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-IELxa0wXsqqEv6FT .taskText0,#mermaid-svg-IELxa0wXsqqEv6FT .taskText1,#mermaid-svg-IELxa0wXsqqEv6FT .taskText2,#mermaid-svg-IELxa0wXsqqEv6FT .taskText3{fill:#fff}#mermaid-svg-IELxa0wXsqqEv6FT .task0,#mermaid-svg-IELxa0wXsqqEv6FT .task1,#mermaid-svg-IELxa0wXsqqEv6FT .task2,#mermaid-svg-IELxa0wXsqqEv6FT .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutside0,#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutside2{fill:#000}#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutside1,#mermaid-svg-IELxa0wXsqqEv6FT .taskTextOutside3{fill:#000}#mermaid-svg-IELxa0wXsqqEv6FT .active0,#mermaid-svg-IELxa0wXsqqEv6FT .active1,#mermaid-svg-IELxa0wXsqqEv6FT .active2,#mermaid-svg-IELxa0wXsqqEv6FT .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-IELxa0wXsqqEv6FT .activeText0,#mermaid-svg-IELxa0wXsqqEv6FT .activeText1,#mermaid-svg-IELxa0wXsqqEv6FT .activeText2,#mermaid-svg-IELxa0wXsqqEv6FT .activeText3{fill:#000 !important}#mermaid-svg-IELxa0wXsqqEv6FT .done0,#mermaid-svg-IELxa0wXsqqEv6FT .done1,#mermaid-svg-IELxa0wXsqqEv6FT .done2,#mermaid-svg-IELxa0wXsqqEv6FT .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-IELxa0wXsqqEv6FT .doneText0,#mermaid-svg-IELxa0wXsqqEv6FT .doneText1,#mermaid-svg-IELxa0wXsqqEv6FT .doneText2,#mermaid-svg-IELxa0wXsqqEv6FT .doneText3{fill:#000 !important}#mermaid-svg-IELxa0wXsqqEv6FT .crit0,#mermaid-svg-IELxa0wXsqqEv6FT .crit1,#mermaid-svg-IELxa0wXsqqEv6FT .crit2,#mermaid-svg-IELxa0wXsqqEv6FT .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-IELxa0wXsqqEv6FT .activeCrit0,#mermaid-svg-IELxa0wXsqqEv6FT .activeCrit1,#mermaid-svg-IELxa0wXsqqEv6FT .activeCrit2,#mermaid-svg-IELxa0wXsqqEv6FT .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-IELxa0wXsqqEv6FT .doneCrit0,#mermaid-svg-IELxa0wXsqqEv6FT .doneCrit1,#mermaid-svg-IELxa0wXsqqEv6FT .doneCrit2,#mermaid-svg-IELxa0wXsqqEv6FT .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-IELxa0wXsqqEv6FT .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-IELxa0wXsqqEv6FT .milestoneText{font-style:italic}#mermaid-svg-IELxa0wXsqqEv6FT .doneCritText0,#mermaid-svg-IELxa0wXsqqEv6FT .doneCritText1,#mermaid-svg-IELxa0wXsqqEv6FT .doneCritText2,#mermaid-svg-IELxa0wXsqqEv6FT .doneCritText3{fill:#000 !important}#mermaid-svg-IELxa0wXsqqEv6FT .activeCritText0,#mermaid-svg-IELxa0wXsqqEv6FT .activeCritText1,#mermaid-svg-IELxa0wXsqqEv6FT .activeCritText2,#mermaid-svg-IELxa0wXsqqEv6FT .activeCritText3{fill:#000 !important}#mermaid-svg-IELxa0wXsqqEv6FT .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-IELxa0wXsqqEv6FT g.classGroup text .title{font-weight:bolder}#mermaid-svg-IELxa0wXsqqEv6FT g.clickable{cursor:pointer}#mermaid-svg-IELxa0wXsqqEv6FT g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-IELxa0wXsqqEv6FT g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-IELxa0wXsqqEv6FT .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-IELxa0wXsqqEv6FT .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-IELxa0wXsqqEv6FT .dashed-line{stroke-dasharray:3}#mermaid-svg-IELxa0wXsqqEv6FT #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT .commit-id,#mermaid-svg-IELxa0wXsqqEv6FT .commit-msg,#mermaid-svg-IELxa0wXsqqEv6FT .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-IELxa0wXsqqEv6FT g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-IELxa0wXsqqEv6FT g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-IELxa0wXsqqEv6FT g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-IELxa0wXsqqEv6FT .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-IELxa0wXsqqEv6FT .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-IELxa0wXsqqEv6FT .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-IELxa0wXsqqEv6FT .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-IELxa0wXsqqEv6FT .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-IELxa0wXsqqEv6FT .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-IELxa0wXsqqEv6FT .edgeLabel text{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-IELxa0wXsqqEv6FT .node circle.state-start{fill:black;stroke:black}#mermaid-svg-IELxa0wXsqqEv6FT .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-IELxa0wXsqqEv6FT #statediagram-barbEnd{fill:#9370db}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-state .divider{stroke:#9370db}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-IELxa0wXsqqEv6FT .note-edge{stroke-dasharray:5}#mermaid-svg-IELxa0wXsqqEv6FT .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-IELxa0wXsqqEv6FT .error-icon{fill:#522}#mermaid-svg-IELxa0wXsqqEv6FT .error-text{fill:#522;stroke:#522}#mermaid-svg-IELxa0wXsqqEv6FT .edge-thickness-normal{stroke-width:2px}#mermaid-svg-IELxa0wXsqqEv6FT .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-IELxa0wXsqqEv6FT .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-IELxa0wXsqqEv6FT .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-IELxa0wXsqqEv6FT .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-IELxa0wXsqqEv6FT .marker{fill:#333}#mermaid-svg-IELxa0wXsqqEv6FT .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-IELxa0wXsqqEv6FT { color: rgba(0, 0, 0, 0.75); font: ; } x1 a1 x2 a2 ..xn an

假设有两个点不是按照顺序一一对应移动的话，则肯定有一段距离是多出来的，即没有必要去走的，所以，按照顺序一一对应去移动的话，当前的每个 $x$ 到最终的位置距离之和一定是最小的。

设最终的距离之和为 $dist\_sum$，则有：$$dist\_sum=|x_1-a_1|+|x_2-a_2|+|x_3-a_3|+...+|x_n-a_n|$$ 由于 $a$ 数列是一个公差为 1 的等差数列，所以我们可以将它们进一步化简为：$$dist\_sum=|x_1-a|+|x_2-1-a|+|x_3-2-a|+...+|x_n-(n-1)-a|$$ 此时就转化成我们熟悉的利用中位数求最小距离和的问题了。 注意：每个 $x$ 只要减去一个相应的按 1 递增的序列数就行，不一定从 0 开始，也可以减去 2，3，4…等等。

代码

#include <cstdio> #include <algorithm> #include <cmath> #define sc scanf #define pf printf using namespace std; typedef long long LL; const int N = 1e4 + 10; int n; int x[N], y[N]; int main() { LL ans = 0; sc("%d", &n); for(int i = 0; i < n; i++) sc("%d %d", &x[i], &y[i]); sort(y, y + n); for(int i = 0; i < n; i++) ans += abs(y[i] - y[n >> 1]); sort(x, x + n); for(int i = 0; i < n; i++) x[i] -= i; sort(x, x + n); for(int i = 0; i < n; i++) ans += abs(x[i] - x[n >> 1]); pf("%lld\n", ans); return 0; }