首页 > 代码库 > 【uva10057】巧妙做法
【uva10057】巧妙做法
这个题之前做过,方法太笨还不对,今天再做突然想到一个巧妙做法,网上应该也有别人用此方法的,因为并不是很难,但我没有看别人的,是自己想出来的哈哈哈
首先要对输入的数组进行排序,这是毋庸置疑的。
因为要计算绝对值的和,所以就想到了数轴上的距离的概念。要使|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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。