uva 10057 - A mid-summer night's dream.
点击打开链接uva 10057
题目意思： 输入一序列数字X1.....Xn 给定一个表达式|X1-A| + |X2-A| + … … + |Xn-A|,要求找到整数A满足这个表达式值是最小的，A可能有多个
解题思路： 1：中位数是指一组数据按照从小到大后中处在中间的位置，它是这组数据里面能够反映数据的集中强度。由于我们要求|X1-A|+......|Xn-A| = |(X1+X2......+Xn)-n*A|，那么我们知道要使得这个表达式的值越小，那么A就必须是这一组数的最集中的数，那么就是A就是中位数。
2：由于数组的个数的不同导致中位数存在差异，并且中位数旁边的数带入这个表达式计算结果也可能相同，所以思路如下
3：思路：1用num数组保存当前的元素，用vis数组保存元素有几个例如vis[i] = 2说明i有2个 2对数组排序，求出中位数 3往中位数的两边枚举直到求出的数值大于最小值 4 输出
4：输出第一个要求输出A的最小值，第二个是输出输入文件中满足的A的个数，第三个是全部A的个数
代码：
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cctype> #include <cctype> #include <cmath> #include <stack> #include <list> #include <set>using namespace std; #define MAXN 1000010int n;int vis[MAXN];long long num[MAXN];set<int>s;//记录全部A的个数//求表达式值long long min_sum(long long x){ long long sum = 0; for(int i = 0 ; i < n ; i++) sum += abs(num[i]-x); return sum;}void solve(){ long long i , j , sum; long long min_A , num_A; long long mid , tmp_sum1 , tmp_sum2; sort(num , num+n) ; s.clear(); if(n%2 == 0) mid = (num[n/2]+num[n/2-1])/2; else mid = num[n/2]; min_A = mid ; s.insert(mid) ; num_A = vis[mid] ; vis[mid] = 0; sum = min_sum(mid); for(i = mid-1 , j = mid+1; ;){ tmp_sum1 = min_sum(i); tmp_sum2 = min_sum(j); if(tmp_sum1 != sum && tmp_sum2 != sum) break; else{ if(tmp_sum1 == sum){ min_A = i ; s.insert(i); if(vis[i]){ num_A++ ; vis[i]--; } i--; } if(tmp_sum2 == sum){ if(vis[j]){ num_A++ ; vis[j]--; } s.insert(j) ; j++; } } } printf("%lld %lld %d\n" , min_A , num_A , s.size());}int main(){ //freopen("input.txt" , "r" , stdin); while(scanf("%d" , &n) != EOF){ memset(vis , 0 , sizeof(vis)); for(int i = 0 ; i < n ; i++){ scanf("%lld" , &num[i]); vis[num[i]]++; } if(n == 1) printf("%lld 1 1\n" , num[0]); else solve(); } return 0; }