给你一个长度为n的数组a,和一个整数s.
你现在可以将数组中的某个数字+1或者-1(同一个数字可以做任意多次操作),请问你需要做多少次这样的操作,才能使得最后这n个数字的中位数等于s.保证n为奇数(即保证最后n个数字的中位数是唯一的).请你输出这个最少的操作次数。Input输入的第一行是两个整数n,s.(1<=n<=2*10^5,1<=s<=10^9)第二行是n个整数a[1..n](1<=ai<=10^9).保证n为奇数。Output输出只有一行,即最少的操作次数。Examples Input
3 8 6 5 8
Output
2
Input
7 20 21 15 12 11 20 19 12
Output
6 首先进行排序，看中位数是否等于s 等于输出0 不等于，看中位数大于还是小于s， 中位数>s： 改中位数为s，同时记录操作次数。因为中位数改小了，所以比它大的还比它大，但比它小的可能会大于它。所以从中位数向左查找，比s大的改为s(操作次数最少)，记录操作次数。 中位数
1 #include2 #include 3 #include 4 #define ll long long 5 using namespace std; 6 7 const int N = 1e6+10; 8 int a[N]; 9 10 int main()11 {12 #ifdef local13 freopen("in.txt","r",stdin);14 #endif // local15 int n, s;16 cin >> n >> s;17 for(int i = 0; i < n; ++i)18 cin >> a[i];19 sort(a,a+n);20 int mid = n/2;21 ll cost;22 if(a[mid] < s)23 {24 cost = s - a[mid];25 for(int i = mid+1; i < n; ++i)26 if(a[i] < s)27 {28 cost += s-a[i];29 }else break;30 cout << cost;31 }32 else if(a[mid] > s)33 {34 cost = a[mid] - s;35 for(int i = mid-1; i >= 0; --i)36 if(a[i] > s)37 {38 cost += a[i]-s;39 }else break;40 cout << cost;41 }42 else43 puts("0");44 return 0;45 }