首页 > 代码库 > uva10057 - A mid-summer night's dream
uva10057 - A mid-summer night's dream
题目: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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。