題意
題目鏈接：P1862 輸油管道問題
不難看出每個油井的 \(x\) 坐標是沒用的，所以問題轉化為如下，
代數意義：給出 \(n\) 個數 \(y_1,y_2,\ldots,y_n\)，找一個數 \(a\)，使得 \(\sum_{i=1}^n |a-y_i|\) 最小，
幾何意義：數軸上有 \(n\) 個點 \(y_1,y_2,\ldots,y_n\)，在數軸上放置一個點 \(a\)，使得線段 \(ay_1,ay_2,\ldots,ay_n\) 長度之和最小，
思路
為便于說明，假設 \(y_1,y_2,\ldots,y_n\) 從小到大有序，
如果從代數意義著手，你會發現式子里既有絕對值又有和式，很難找到思路，所以應該從幾何意義著手，
當 \(n\) 為偶數時，\(a\) 放在最中間兩個點之間是最優的，證明如下：首先只考慮 \(y_1\) 和 \(y_n\) 兩個點，則點 \(a\) 應放在 \(y_1\) 和 \(y_n\) 中間，接著再把點 \(y_2\) 和點 \(y_{n-1}\) 納入考慮，顯然 \(a\) 應該放在 \(y_2\) 和 \(y_{n-1}\) 中間（此時 \(a\) 同樣也在 \(y_1\) 和 \(y_n\) 中間）……依此類推即可得出結論，
當 \(n\) 為奇數時，\(a\) 放在中間那個點上是最優的，證明方法同上，
統一處理：取 \(y_{\lfloor\frac{n+1}{2}\rfloor}\) 作為 \(a\)，或者取中位數也行，可以直接排個序取中間，也可以按快排的思想用分治法求，反正都能過，
代碼
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 5;
int arr[maxn];
int solve(int n)
{
sort(arr + 1, arr + 1 + n);
int a = arr[(n + 1) / 2];
int ans = 0;
for (int i = 1; i <= n; i++)
ans += abs(arr[i] - a);
return ans;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
arr[i] = y;
}
printf("%d", solve(n));
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/243500.html
標籤：其他