参考：

【题意】

n个有序序列的归并排序.每次可以选择不超过k个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过T, 问k最小是多少。

【思路】

k越大，代价越小，二分k，check k

对于每个k，问题转化为n个结点的最优k叉树，用堆做时间复杂度为O(nlogn)，再加上二分总复杂度是O(nlogn^2)

然后T了。。。听说加输入挂可以卡过去

正解是这样的：

原数组排序，预处理时间复杂度O(nlogn)

然后求最优k叉树，用一个队列维护合并后的值，而不需要加入原来的堆里重排序（利用新加入的内结点本身的单调性），每次时间复杂度为O(n)

O(nlogn)+O(logn)*O(n)，所以最后时间复杂度是O(nlogn)

n个结点不一定能构成最优k叉树，需要补 k-1-((n-1)%(k-1))个权为0的虚结点。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 typedef long long ll;10 int n;11 ll t;12 const int maxn=1e5+3;13 ll a[maxn];14 bool judge(int mid){15 int cnt=(n-1)/(mid-1);16 queue
             
               Q;17 if((n-1)%(mid-1)!=0){18 cnt++;19 for(int i=0;i<(mid-1-(n-1)%(mid-1));i++){20 Q.push(0);21 } 22 }23 ll ans=0;24 int l=0;25 while(cnt--){26 ll tmp=0;27 for(int i=0;i
              
               =n||Q.front()<=a[l])){29 tmp+=Q.front();30 Q.pop();31 }else{32 tmp+=a[l++];33 }34 }35 ans+=tmp;36 Q.push(tmp);37 }38 if(ans<=t) return true;39 return false;40 }41 int main(){42 int T;43 scanf("%d",&T); 44 while(T--){45 scanf("%d%lld",&n,&t);46 for(int i=0;i
               
                >1;53 if(judge(mid)){54 r=mid-1;55 }else{56 l=mid+1;57 }58 }59 printf("%d\n",l);60 }61 return 0;62 }
               
              
             
            
           
          
         
        
       
      

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;int n;ll t;const int maxn=1e5+3;ll a[maxn];bool judge(int mid){ queue
            
              Q1,Q2; for(int i=0;i
             
              =mid){ ll tmp=0; for(int i=0;i
              
               >1; if(judge(mid)){ r=mid-1; }else{ l=mid+1; } } printf("%d\n",l); } return 0;}