题目描述
The only difference between easy and hard versions is the number of elements in the array.
You are given an array a consisting of n integers. In one move you can choose any ai and divide it by 2 rounding down (in other words, in one move you can set ai:=?ai2?).
You can perform such an operation any (possibly, zero) number of times with any ai.
Your task is to calculate the minimum possible number of operations required to obtain at least k equal numbers in the array.
Don’t forget that it is possible to have ai=0 after some operations, thus the answer always exists.
Input
The first line of the input contains two integers n and k (1≤k≤n≤2?105) — the number of elements in the array and the number of equal numbers required.
The second line of the input contains n integers a1,a2,…,an (1≤ai≤2?105), where ai is the i-th element of a.
Output
Print one integer — the minimum possible number of operations required to obtain at least k equal numbers in the array.
Examples
Input
5 3
1 2 2 4 5
Output
1
Input
5 3
1 2 3 4 5
Output
2
Input
5 3
1 2 3 3 3
Output
0
题目大意
给你一个数组a[]包含n个数，你可以进行如下操作：选择任意一个a[i]然后除以2（下取整）。问最少需要多少次操作才能使数组中有至少k个数相等。
题目分析
我们可以保存所有a[i]通过操作的产生的所有数，并记录变成这个数需要的步数，并统一的存到某个数组中去。
cnt[i] //记录a[]中有多少个数通过操作可以变成i
sum[i] //记录a[]中的那些能变成i的数变成i需要的操作次数的和
当cnt[i]的值到了k时，说明变成i是一个可行解，将sum[i]中记录的操作次数与ans进行比较，最后找出最小值即可。
代码如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N=2e5+5;
int a[N];
int sum[N],cnt[N];
int main()
{int n,k;scanf("%d %d",&n,&k);for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n); //要先排序（这样才能保证sum[i]中记录的解为变成i的最优解）int ans=1e9;for(int i=0;i<n;i++){int s=a[i]; //s为a[i]可以变成的数int t=0; //记录操作次数while(s){cnt[s]++; //a[i]可以变成s,用cnt[s]记录sum[s]+=t; //记录变成s需要的操作次数if(cnt[s]==k) ans=min(ans,sum[s]);t++;s>>=1; //更新s}}printf("%d\n",ans);return 0;
}