題目大意：
對于給出的n個冰激凌球的大小，滿足下面的球的大小是上一個的至少2倍，對于給出的k（由k的冰激凌球才能算作一個冰激凌塔），問n個冰激凌球可以最多堆出多少個高度為k的冰激凌塔
題目分析：
對于n個冰激凌球，顯然我們得知可以堆出的高度為k的塔的數量在0~[n / k]之間，這里可以通過二分遍歷每一種可能，初始時二分邊界l==0，r==[n / k]，每次取中間值mid=（l+r）/ 2，判斷mid高度為k的塔能否堆出，如果可以則嘗試mid為更大，否則則嘗試mid為更小時，不斷二分嘗試mid是否可行，而對于每個mid，我們要寫一個判斷函式，來判斷mid座高度為k的冰激凌塔能否堆出，這里用到了貪心的思維，我們先對n個冰激凌球的大小進行從小到大的排序，然后對于mid座塔我們只要創建一個一維陣列，0~mid-1放置排完序的冰激凌球的前mid個（由于已經將冰激凌球排序，取出前mid個放入這個陣列即可），然后回圈k-1遍（因為高度初始已經為1，只要再判斷k-1層的情況即可），從編號為mid開始依次選取冰激凌球（從小到大）與這個0~mid-1個位置進行比較，如果滿足是它的至少兩倍則更新0~mid-1位置的冰激凌球大小，否則繼續往后找一個滿足的冰激凌球去替換它，完成了一層之后則繼續從0~mid-1開始（共k層），假如中途出現冰激凌球已經遍歷到最后，但是還是k層冰激凌塔沒有完成堆疊，則回傳失敗，否則在結束所有k層的每個判斷后回傳成功
關于貪心的部分，由于陣列是從小到大排序的，如果遇到一個位置不滿足是它的至少兩倍則將下標往后移動，前面的就被舍棄了（因為對后面的位置來說，它一定是比前面位置大的，指向該下標的冰激凌球大小如果不滿足前者至少兩倍，則不可能滿足后者的至少兩倍關系，而從小到大排序選擇也是滿足了最優的選擇方案，先用小的試探，后用大的試探，小的一定在前面）
代碼：
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 6 const int M = 300005; 7 long long ice[M]; 8 long long update[M]; 9 int n, k; 10 11 bool judge(int x){ //x代表判斷做x個塔是否可行 12 for(int i = 0; i < x; i++){ 13 update[i] = ice[i]; 14 } 15 int cnt = x; 16 for(int i = 1; i < k; i++){ 17 for(int j = 0; j < x; j++){ 18 while(update[j]*2 > ice[cnt] && cnt < n) cnt++; 19 if(cnt == n) return false; 20 update[j] = ice[cnt]; 21 cnt++; 22 } 23 } 24 return true; 25 } 26 27 int main(){ 28 int t; 29 scanf("%d", &t); 30 int cnt = 1; 31 while(t--){ 32 scanf("%d%d", &n, &k); 33 for(int i = 0; i < n; i++) scanf("%lld", &ice[i]); 34 sort(ice, ice + n); 35 int l = 0; 36 int r = n/k; 37 int ans = 0; 38 while(l <= r){ 39 int m = (l+r)/2; 40 if(judge(m)){ 41 l = m+1; 42 ans = m; 43 }else{ 44 r = m-1; 45 } 46 } 47 printf("Case #%d: %d\n", cnt++, ans); 48 } 49 return 0; 50 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135939.html
標籤：其他
上一篇：閑的
下一篇：C++洗掉排序陣列中的重復項