【題解】ZeroJudge e606: 10057 – A mid-summer nights dream

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e606
【解題想法】

  • 要讓 (|X1 − A| + |X2 − A| + . . . + |Xn − A|) 的值最小,A 是 (X1,X2,…,Xn) 的中位數。
  • 先對 a[ ] = (X1,X2,…,Xn) 進行排序,由小排到大。
  • 如果 n 是偶數,中位數有兩個, mid1 = a[(n-1)/2] 和 mid2 = a[n/2]
  • 如果 n 是奇數,中位數只有一個,mid1 = mid2。
  • 【例子】a[ ] = {1, 3, 4, 6, 7, 10}
    • 中位數有兩個, mid1 = 4, mid2 = 6。
    • A = 4, delta = {3, 1, 0, 2, 3, 6}, sum = 15
    • A = 5, delta = {4, 2, 1, 1, 2, 5}, sum = 15
    • A = 6, delta = {5, 3, 2, 0, 1, 4}, sum = 15
  • 題目要求輸出三個整數:
    • 第一個數字是能使該算式最小的最小的 A:mid1
    • 第二個數字是|Xi − A|為最小值 (= 0) 的數量:Xi = mid1 or Xi = mid2
    • 第三行數字是有幾種可能的 A:mid2 – mid1 + 1
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    int n;
    while (cin >> n){
        int a[n];
        for (int i = 0; i < n; i++){
            cin >> a[i];
        }
        sort(a, a+n);
        int mid1 = a[(n-1)/2];
        int mid2 = a[n/2];
        int ans = 0;
        for (int i = 0; i < n; i++){
            if (a[i] == mid1 || a[i] == mid2) ans++;
        }
        cout << mid1 << " " << ans << " " << mid2 - mid1 + 1 << "\n";
    }
    return 0;
}

分享本文 Share with friends