a941: 10041 - Vito's large family

解題心得

vito family的進化版(?)，如果直接重跑過一遍s[]把距離加起來會tle。

但最後還是用了黑魔法的那兩行才過的。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;

int s[2000000] = { 0 },record[30001] = { 0 };

int main()
{
	cin.sync_with_stdio(false), cin.tie(0);
	int t, r;
	cin >> t;
	while (t--)
	{
		cin >> r;
		for (int i = 0; i < 30001; i++)
			record[i] = 0;
		for (int i = 0; i < r; i++)
		{
			cin >> s[i];
			record[s[i]]++;
		}
		sort(s, s + r);
		int mid = 0;
		long long int d = 0;
		if (r % 2 == 1) mid = s[r / 2];
		else mid = s[r / 2 - 1];
		for (int i = 0; i <= 30000; i++)
		{
			d += abs(i - mid) * record[i];
		}
		cout << d << " " << mid << endl;
	}
	return 0;
}