题意

给你n个序列以及序列内元素个数，现要求进行归并，花费为归并过程中序列长度的和，给定一个花费T，问最小的k(每次归并的最大序列个数)为多少。

 

分析

首先应该想到的是二分。然后思考如何check呢。排序，贪心的来，每次都选最小的前若干个。要注意的是，最后k-1个当然是在最后一次归并，那么要满足这样的情况，我们要判断(n-1)%(k-1)是否有剩余，有的话就先进行一次[余数+1]的归并，这样就保持了最优。

 

 

#include 
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;const int maxn=1e5+10;int t,n;int a[maxn],sum[maxn];priority_queue< int, vector
                
                  , greater
                 
                   > q;bool check(int k){ while( !q.empty() ) q.pop(); int m=(n-1)%(k-1); int res=0; if(m){ m++; res+=sum[m]; q.push(res); } for(int i=m+1;i<=n;i++) q.push(a[i]); int up=(n-1)/(k-1); for(int i=0;i
                  
                   t) return false; return true;}int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&t); sum[0]=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; int l=2,r=n,mid; while(l
                   
                    >1; if(check(mid)) r=mid; else l=mid+1; } if(n<=1) r=1; cout<
                    
                     <