uva - 10057 - A mid-summer night's dream. (数学、中位数)

题意:给你一串数字,求满足  (|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;
	}
}


uva - 10057 - A mid-summer night's dream. (数学、中位数)

上一篇:用 SpriteKit 做一个逃逸游戏 (4)


下一篇:用 SpriteKit 做一个逃逸游戏 (5)