这个题之前做过,方法太笨还不对,今天再做突然想到一个巧妙做法,网上应该也有别人用此方法的,因为并不是很难,但我没有看别人的,是自己想出来的哈哈哈
首先要对输入的数组进行排序,这是毋庸置疑的。
因为要计算绝对值的和,所以就想到了数轴上的距离的概念。要使|X1-A|+|X2-A|最小,也就是要找一个点A,使其到X1,X2距离和最短,所以很容易想到在数轴上只要A在X1和X2之间就行。
对排序后的数组进行操作,将首尾(最小值和最大值)抽取出来,A只要介于他俩之间就行,同理再将第二位和倒数第二位抽取出来,A要介于他俩之间才行......如此剥离下去,最后只会剩余一项或是两项。
所以提前判断数组的奇偶性,奇数的话A就是中间那项(很容易吧)偶数的话就是介于两数之间的所有数A都可以取,也就是有多个A值,但是最小的A值肯定还是左边的,因为右边的只会大于等于左边的。
计算有多少个A存在于数组中的时候,用到了algorithm算法自带的上下界函数(upper_bound()和lower_bound()),很好用的。
上ac代码,也是一次就过了哈哈哈
#include <iostream> #include<algorithm> #include<cmath> using namespace std; int num,minA,numA,arr[1000005]; int main(){ while(cin>>num){ for (int i=0;i<num;i++){ cin>>arr[i]; } sort(arr,arr+num); //check the parity if (num%2==1){ //odd minA = arr[(num-1)/2]; numA = upper_bound(arr,arr+num,minA)-lower_bound(arr,arr+num,minA); cout<<minA<<" "<<numA<<" "<<"1"<<endl; } else{ //even int a1=arr[num/2-1]; int a2=arr[num/2]; minA=a1; if (a1==a2){ numA=upper_bound(arr,arr+num,minA)-lower_bound(arr,arr+num,minA); cout<<minA<<" "<<numA<<" "<<"1"<<endl; } else{ numA=upper_bound(arr,arr+num,a2)-lower_bound(arr,arr+num,a1); cout<<minA<<" "<<numA<<" "<<a2-a1+1<<endl; } } } return 0; }
原文:http://blog.csdn.net/monkeyduck/article/details/28860265