123. 士兵(货仓选址问题)

AcWing 123. 士兵

题目大意

士兵散落在各个坐标上,士兵可以上下左右移动,以所有士兵最少步数的方式使得士兵在同一水平线上(y相同),一个位置只能有一名士兵,不可重叠。

思路

  • x和y坐标是互不影响的,也就是说可以先安排y坐标再安排x坐标。
  • 假设y方向上的水平线在d处,那么y方向上的移动步数就为 ∑ i = 0 n − 1 ∣ y i − d ∣ \sum_{i = 0}^{n-1}\left | y_i - d \right | i=0n1yid,这就是经典货仓选址问题,d直接取y排序后的中位值就最少。
  • 而x方向上排序后(因为输入是无规律的,需要排序整理)的相对顺序可以看成是最终的相对顺序,然后假设 x 0 x_0 x0的位置是a,那么 x 1 x_1 x1的位置就是a+1, x i x_i xi位置就为a+i,那么总步数就是 ∑ i = 0 n − 1 ∣ x i − ( a + i ) ∣ \sum_{i = 0}^{n-1}\left | x_i - (a+i) \right | i=0n1xi(a+i),可化成 ∑ i = 0 n − 1 ∣ ( x i − i ) − a ∣ \sum_{i = 0}^{n-1}\left | (x_i-i) - a \right | i=0n1(xii)a,那么就将问题转成货仓选址了,a直接取序列 ( x i − i ) (x_i-i) (xii)排序后的中位值,会使整个式子值最小。
  • 参考文章
#include
#include
#include
using namespace std;
const int N = 10010;
int a[N],b[N];
int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n; cin>>n;
    for(int i = 0; i < n; i++){
        cin>>a[i]>>b[i];
    }
    sort(b,b+n);
    sort(a,a+n);
    int mid = b[n/2], ans = 0;
    for(int i = 0; i < n; i++)
        ans += abs(b[i]-mid);
    for(int i = 0; i < n; i++)
        a[i] -= i;
    sort(a,a+n);
    mid = a[n/2];
    for(int i = 0; i < n; i++)
        ans += abs(a[i]-mid);
    cout<<ans;
    return 0;
}

你可能感兴趣的