uva - 10041 - Vito's Family(数学)

题意:

世界闻名的黑社会老大Vito Deadstone要搬到纽约来了。在那裡他有一个大家族,并且他们都住在Lamafia大道上。因為Vito时常要拜访所有的亲戚,他想要找一间离他们最近的房子,也就是说他希望从他的家到所有的亲戚的家的距离的和為最小。
他恐吓你写一个程式来帮助帮助他解决这个问题。
输入的第一列有一个整数代表以下有多少组测试资料。

每组测试资料一列,第一个整数 r(0 < r < 500),代表他亲戚的数目。接下来的r个整数s1,s2,......sr為这些亲戚房子的门牌号码(0 < si <30000)。注意:有些亲戚的门牌号码会相同。

方法:遍历的方法TLE,稍稍优化了下还是超时,其实不用想也知道,只是表面上优化,当r = 499,s从1到29999的情况还是没优化。

采用的方法找中间的那个亲戚的位置,从那个位置算到其他亲戚的距离和,取最小。

uva - 10041 - Vito's Family(数学)

uva - 10041 - Vito's Family(数学)

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAX 500

int main()
{
#ifdef Local
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int t = 0, n = 0, i = 0, j = 0, min = 0;
	int rel[MAX];
	cin >> t;
	while (t--)
	{
		min = 1 << 30;
		cin >> n;
		for (i = 0; i < n; i++)
		{
			cin >> rel[i];
		}
		sort(rel, rel+n);
		int sum = 0;
		for (i = 0; i < n; i++)
			sum += abs(rel[n/2] - rel[i]);
		cout << sum << endl;
	}
}


TLE代码:

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAX 500

int main()
{
#ifdef Local
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int t = 0, n = 0, i = 0, j = 0, min = 0, min_r = 0, max_r = 0;
	int rel[MAX];
	cin >> t;
	while (t--)
	{
		min_r = 1 << 30, max_r = 0;
		min = 1 << 30;
		cin >> n;
		for (i = 0; i < n; i++)
		{
			cin >> rel[i];
			if (rel[i] > max_r)
				max_r = rel[i];
			if (rel[i] < min_r)
				min_r = rel[i];
		}
		for (i = min_r; i <= max_r; i++)
		{
			int sum = 0;
			for (j = 0; j < n; j++)
				sum += abs(rel[j] - i);
			if (sum < min)
				min = sum;
		}
		cout << min << endl;
	}
}


uva - 10041 - Vito's Family(数学)

上一篇:JavaWeb8.6【CSS案例:注册页面(html+css)】


下一篇:UVa 11992 Fast Matrix Operations / 线段树成段更新