As we all know, Coach Gao is a talented chef, because he is able to cook M dishes in the same time. Tonight he is going to have a hearty dinner with his girlfriend at his home. Of course, Coach Gao is going to cook all dishes himself, in order to show off his genius cooking skill to his girlfriend.
To make full use of his genius in cooking, Coach Gao decides to prepare N dishes for the dinner. The i-th dish contains Ai steps. The steps of a dish should be finished sequentially. In each minute of the cooking, Coach Gao can choose at most M different dishes and finish one step for each dish chosen.
Coach Gao wants to know the least time he needs to prepare the dinner.
Input There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers N and M (1 <= N, M <= 40000). The second line contains N integers Ai (1 <= Ai <= 40000).
Output For each test case, output the least time (in minute) to finish all dishes.
Sample Input 2 3 2 2 2 2 10 6 1 2 3 4 5 6 7 8 9 10 Sample Output 3 10
思路及题意： n道菜，同时可做m道菜，一次做m道菜的一个步骤， 下面一行是没道菜做成功所需的步骤 一开始以为是贪心题，但不好贪，且数据大，所以找规律 规律就是所有菜所需步骤加起来除以m。若有余数，则cnt++ 若还小于最大步骤，则输出最大步骤，不小于则输出cnt n<=m，则直接输出最大步骤
#include<bits/stdc++.h> const double PI=acos(-1.0); using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define lowbit(x) x&-x #define inf 0x3f3f3f3f #define pr pair<int,int> typedef pair<char,int> PAIR; struct CmpByValue { bool operator()(const PAIR& lhs, const PAIR& rhs) { return lhs.second > rhs.second; } }; //priority_queue<int,vector<int>,greater<int>> pp; const int mod = 123456789 ; const int M = 4e5 +10 ; const int limt = 1<<20; const int INF = 1e9; typedef long long ll; ll t,m,n,maxn,cnt,sum; int mp[M]; /* n道菜，同时可做m道菜，一次做m道菜的一个步骤， 下面一行是没道菜做成功所需的步骤 一开始以为是贪心题，但不好贪，且数据大，所以找规律 规律就是所有菜所需步骤加起来除以m。若有余数，则cnt++ 若还小于最大步骤，则输出最大步骤，不小于则输出cnt n<=m，则直接输出最大步骤 */ int main() { ios::sync_with_stdio(0); cin>>t; while(t--) { sum=0; cin>>n>>m; for(ll i=0; i<n; i++) { cin>>mp[i]; sum+=mp[i]; } sort(mp,mp+n); maxn=mp[n-1];//最大值 cnt=sum/m;//规律 if(cnt*m!=sum)//有余数 cnt++; if(n<=m||cnt<maxn) cout<<maxn<<endl; else if(cnt>=maxn) cout<<cnt<<endl; } return 0; }