【題目描述】

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.InputThe first line of the input contains two integers n and k (1≤k≤n≤50) — 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.OutputPrint one integer — the minimum possible number of operations required to obtain at least k equal numbers in the array.ExamplesInput 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

【題目分析】
敢想不敢做系列，總覺得是一個貪心或者什么的，但是沒有想到什么好的策略。暴力吧又不敢寫，10⁵的數據暴力，emmm。
在網上查了一下題解，發現還真是一個暴力，只不過這種暴力的思想我還是沒有想到，主要是人家用到vector開二維數組，我覺得肯定會爆空間就沒想到用二維數組。
用一個二維數組$vis[i][j]$j變成i需要多少步，這樣我們找到含有k個以上數字可以變成他的vis[i]然后找需要步數最小的。不明白可以看代碼，很暴力的做法。
我把看的題解的代碼稍微改動了一下，稍微進行了優化，首先，我將整個數組進行排序，然后按照這個順序建立的二維數組肯定是有序的，對于每個i，肯定是j越小所用步數越小的在前面，這樣就不用每個都進行排序了（竟然排序都能過）。還有就是加上了一個剪枝，如果當前步數已經大于前面找到的答案直接退出。
還是要敢想敢做啊，不要被復雜度蒙蔽了雙眼什么都不敢做。就算TLE了也比什么都做不出來強。（當然如果是DP然后還想暴力那就emmm了）
【AC代碼】

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<cstdlib> #include<set> #include<map> #include<vector>using namespace std;typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=2e5+5; vector<int> vis[MAXN]; int a[MAXN]; int n,k,ans;int main() {int t,step,tmp;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n);for(int i=0;i<n;i++){t=a[i];step=0;vis[t].push_back(step++);while(t){t>>=1;//先除2，這樣可以將0也計算進去vis[t].push_back(step++);}}ans=INT_MAX;for(int i=0;i<MAXN;i++){if(vis[i].size()<k) continue;tmp=0;for(int j=0;j<k;j++){tmp+=vis[i][j];if(tmp>ans) break;}if(tmp<ans) ans=tmp;}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的cf#582div3 D——暴力的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。