题意:给你一串数字,求满足 (|X1-A| + |X2-A| + … … + |Xn-A|) is minimum. 这个公式的A,题目要求输出三个数字,三个数字的意思是。1、最小的A。2、一串数中满足这个公式的所有A。第三个不太理解,好像是不只是一串数的了,是所有的数字中满足那个前边求出来minimum的。
方法:就是中位数的问题,先排序,然后分为奇数和偶数处理,奇数的下标为n/2,偶数下标为两个,n/2和n/2+1。WA一次是下标写错了,一次是第一个函数没分奇偶。第三个数说下,如果是奇数,那么只有一个,偶数的话只那两个数之间(含两个数)的数字个数。
#include <iostream> #include <iomanip> #include <string> #include <cstring> #include <cstdio> #include <queue> #include <stack> #include <algorithm> #include <cmath> using namespace std; int n, x, y, z; int num[1000000]; void Input() { int i; for (i = 0; i < n; i++) cin >> num[i]; } void Handle_1() { if (n % 2 == 1) x = num[n/2]; else x = num[n/2-1]; } void Handle_2() { int i = 0; if (1 == n % 2) { for (i = 0; i < n; i++) { if (num[i] == num[n/2]) y++; } } else { for (i = 0; i < n; i++) { if (num[i] == num[n/2] || num[i] == num[n/2-1]) y++; } } } void Handle_3() { if (n % 2 == 1) z = 1; else z = num[n/2] - num[n/2-1] + 1; } int main() { #ifdef Local freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif int i = 0, j = 0; while (cin >> n) { memset(num, 0, sizeof(num)); z = 0, y = 0, z = 0; Input(); sort(num, num+n); Handle_1(); Handle_2(); Handle_3(); cout << x << " " << y << " " << z << endl; } }