点击打开链接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;
}
分享到:
相关推荐
用C语言实现,用较简单的方法实现找中间数
uva705 Slash Maze 的代码,在UVaOJ上通过
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
uva532 Dungeon Master的源代码,并且AC了
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
PDF试题