Time Limit: 2 Sec     Memory Limit: 128 Mb     Submitted: 94     Solved: 27    

---

Description

作为老人的小明非常忧伤，因为他马上要被流放到本部去了，住进全左家垅最有历史感的11舍真是一件非常荣幸的事情。

搬行李是个体力活，小明发现自己的行李太多啦，所以他决定去买很多个袋子来装走。到了超市的小明发现，不同大小的袋子居然价格一样？？？虽然买最大的自然最赚，但是小明是名远近闻名的环保人士，他觉得袋子只要能装下他的行李就够了，并且为了不麻烦收银的小姐姐(⊙o⊙)…，他也只会购买同一种大小的袋子。因此他希望在能装下所有行李的前提下，袋子越小越好。同时为了避免弄乱行李，小明希望同一个袋子装的是位置连续相邻的行李。

小明摸了摸口袋发现自己带的钱最多能买N个袋子，数学特别差的他不知道到底该买多大的才合适，所以想靠你来解决这个问题了。

Input

第一行为一个数字T（T<=10）表示数据组数

第二行为两个数字N（N <= 10^5）和 M（M <= 10^5）表示袋子个数和小明的行李个数

第三行为M个数字，第i个数字a[i]表示小明的第i个行李体积为a[i]（0<a[i] <= 10^9）

Output

输出一行表示袋子的最小体积（整数）

Sample Input

13 31 1 1

Sample Output

1

Hint

袋子不能装下体积大于其容积的物品

多个物品满足体积之和小于等于一个袋子的容积，就能被装进

Source

2017年8月月赛

Author

卢铭威

 

 

 

题解：

二分袋子的体积就好了

、

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7  long long int a[100100]; 8 int n,m; 9 bool jug(long long int x)10 {11     int k=1;12     long long int sum=0;13     for(int i=1;i<=m;++i)14     {15         if(a[i]+sum<=x)16         {17             sum+=a[i];18         }19         else20         {21             sum=a[i];22             k++;23         }24     }25     if(k>n)return false;26     return true;27 }28 int main()29 {30     int T;31 32     scanf("%d",&T);33     while(T--)34     {35         long long int r=0;36          long long int l=0;37 38         long long int mid;39         scanf("%d %d",&n,&m);40         for(int i=1; i<=m; i++)41         {42             scanf("%lld",&a[i]);43             l=max(l,a[i]);44             r+=a[i];45         }46 47         while(l<=r)48         {49             mid=(l+r)>>1;50             if(jug(mid))51             r=mid-1;52             else53             l=mid+1;54         }55         printf("%lld\n",mid);56     }57 58     return 0;59 }