一开始想的是枚举k，然后用前缀和找最小的前k个。
但是这样其实是不对的，因为后面加入的数应该和原来的数都重新排序再找最小的k个。
那么，这里就是个小顶堆了。
但是这时显然枚举k，然后小顶堆检查复杂度不够。
观察可以发现，k是满足二分性质的。k越大花费就会越小。（证明略~显而易见）
那么就可以二分，然后小顶堆检查。
这里有个地方，就是如果我们最后一轮没取够k个数，那么我们就可以有更优的取法。
即一开始不取满k个，然后保证最后一次取满k个，这样才是最优的选择。
那么，我们可以去插入0来满足最后一次取满k个。
最后一次取满k个的条件就是Q.size()-1 % (k-1) == 0
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5+5; const int M = 2e4+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){/*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int n,a[N]; LL T; priority_queue<LL,vector<LL>,greater<LL> > SS; bool check(int k) { priority_queue<LL,vector<LL>,greater<LL> > Q; Q = SS; while( (Q.size()-1)%(k-1) ) Q.push(0); LL ans = 0; while(Q.size() > 1) { LL ma = 0; for(rg int i = 1;i <= k;++i) { ma += Q.top(); Q.pop(); } ans += ma; if(ans > T) return false; Q.push(ma); } return true; } int main() { n = read(),T = read(); for(int i = 1;i <= n;++i) a[i] = read(),SS.push(a[i]); sort(a+1,a+n+1); int L = 2,r = n,ans = n; while(L <= r) { int mid = (L+r)>>1; if(check(mid)) { ans = mid; r = mid-1; } else L = mid+1; } printf("%d ",ans); system("pause"); }