题目:uva10057 - A mid-summer night‘s dream
题目大意:给出n个数,A使得 (|X1-A| + |X2-A| + … … + |Xn-A|) is minimum,求最小的A,输入中A的个数,不同的A的个数。(A可能有多个值)
解题思路:要使得上面的式子最小,找出这个N个数的中位数。如果是奇数个数,那么中位数只有一个,不同的A的个数也只有一个。如果A是偶数的话,那么中位数就由两个,那么找输入中的A的个数就要找来两个值的出现的个数和,不同的A的个数就是右边的中位数 - 左边的中位数 + 1;
例子:
3 5 6 9 11 13 中位数 6 和 9
3 5 6 | 9 11 13
偏差 3 1 0 | 3 5 7 A = 6
左半边加1,右半边减1 这样偏差的和还是最小
4 2 1 |2 4 6 A = 7
5 3 2 |1 3 5 A = 8
6 4 1 |0 2 4 A = 9 右半边有一个值为0了说明不能再减下去了
所以可能的A : 6 7 8 9
代码:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; const int N = 1000005; int n; int num[N]; int main () { int mm, count, ans; while (scanf ("%d", &n) != EOF) { for (int i = 0; i < n; i++) scanf ("%d", &num[i]); sort (num, num + n); count = 0; if (n % 2) { mm = num[n / 2]; for (int i = n / 2; i >= 0 && num[i] == mm; i--) count++; for (int i = n / 2 + 1; i < n && num[i] == mm; i++) count++; ans = 1; } else { int left = num[n / 2 - 1]; int right = num[n / 2]; mm = left; for (int i = n / 2 - 1; i >= 0 && num[i] == left; i--) count++; for (int i = n / 2; i < n && num[i] == right; i++) count++; ans = right - left + 1; } printf ("%d %d %d\n", mm, count, ans); } return 0; }
uva10057 - A mid-summer night's dream,布布扣,bubuko.com
uva10057 - A mid-summer night's dream
原文:http://blog.csdn.net/u012997373/article/details/38237109