题意:
他恐吓你写一个程式来帮助帮助他解决这个问题。
输入的第一列有一个整数代表以下有多少组测试资料。
每组测试资料一列,第一个整数 r(0 < r < 500),代表他亲戚的数目。接下来的r个整数s1,s2,......sr為这些亲戚房子的门牌号码(0 < si <30000)。注意:有些亲戚的门牌号码会相同。
方法:遍历的方法TLE,稍稍优化了下还是超时,其实不用想也知道,只是表面上优化,当r = 499,s从1到29999的情况还是没优化。
采用的方法找中间的那个亲戚的位置,从那个位置算到其他亲戚的距离和,取最小。
#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; } }