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 1000010

int 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;  
}