2011-09-22 08:45:34Morris
a242. 第三題：絕對值總和的最小值
a242. 第三題：絕對值總和的最小值
內容 ：
請你寫一個程式，輸入2n個正整數值 a1, x1, a2, x2 ...... an, xn 且 a1|x1, a2|x2 ...... an|xn
求下列的最小值 |a1x - x1| + |a2x - x2| + ... + |anx - xn| ……
求下列的最小值 |a1x - x1| + |a2x - x2| + ... + |anx - xn| ……
輸入說明
：
有m(1≤m≤5)組測試資料且 |a1 + a2 + ... + an| ≤ 200000 或 1 ≤ n ≤ 100000，每組測試資料第一行為n
接下來共有n行，每行有 2 個整數第 i 行 ai, xi 且由空格隔開整數。
輸出說明
：
對於每一組測試資料，輸出一行一個數字，代表這個最小值。
範例輸入 ：
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? 時的微分
*/
作法 : 數學, 微分
|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? 時的微分
*/