Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

請你寫一個程式，輸入2n個正整數值 a₁, x₁, a₂, x₂ ...... a_n, x_n 且 a₁|x₁, a₂|x₂ ...... a_n|x_n 
求下列的最小值 |a₁x - x₁| + |a₂x - x₂| + ... + |a_nx - x_n| ……

有m(1≤m≤5)組測試資料且 |a₁ + a₂ + ... + a_n| ≤ 200000 或 1 ≤ n ≤ 100000，每組測試資料第一行為n

接下來共有n行，每行有 2 個整數第 i 行 a_i, x_i 且由空格隔開整數。

2
1
1 1
3
1 1
1 2
100000 100000

0
1

板橋高中2011能力競賽 (管理：snail)

---

作法 : 數學, 微分
 |a1x - x1| + |a2x - x2| + ... + |anx - xn| ……
=>a1|x - t1| + a2|x - t2| + ... + an|x - tn| ……
=> sort t1 < t2 < t3 ...
=> f'(i) = a1 + a2 + ... + ai - a(i+1) - ... - an
=> 當 x = t? 時的微分

/**********************************************************************************/
/*  Problem: a242 "第三題：絕對值總和的最小值" from 板橋高中2011能力競賽*/
/*  Language: C (1140 Bytes)                                                      */
/*  Result: AC(64ms, 3.8MB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2011-09-22 07:44:21                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int ai, xi, ti;
}f_of_x;
f_of_x D[100000];
int cmp(const void *a, const void *b) {
    f_of_x *i, *j;
    i = (f_of_x *)a, j = (f_of_x *)b;
    if(i->ti != j->ti)
        return i->ti - j->ti;
    return i->ai - j->ai;
}
int f(int x, int n) {
    int i, sum = 0;
    for(i = 0; i < n; i++)
        sum += D[i].ai * abs(x - D[i].ti);
    return sum;
}
int main() {
    int m, n, i;
    scanf("%d", &m);
    while(m--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d %d", &D[i].ai, &D[i].xi);
            D[i].ti = D[i].xi/D[i].ai;
        }
        qsort(D, n, sizeof(f_of_x), cmp);
        int sum_ai = 0, right_ai = 0, left_ai = 0;
        for(i = 0; i < n; i++)
            sum_ai += D[i].ai;
        for(i = 0; i < n; i++) {
            left_ai += D[i].ai;
            right_ai = sum_ai - left_ai;
            if(left_ai - right_ai >= 0)
                break;
        }
        int min_ti = D[i].ti;
        printf("%d\n", f(min_ti, n));
    }
    return 0;
}
/*
 |a1x - x1| + |a2x - x2| + ... + |anx - xn| ……
=>a1|x - t1| + a2|x - t2| + ... + an|x - tn| ……
=> sort t1 < t2 < t3 ...
=> f'(i) = a1 + a2 + ... + ai - a(i+1) - ... - an
=> 當 x = t? 時的微分
*/