HDU 5884 Sort

题目链接

题目大意

有n堆果子，每堆果子有ai个，一次可以将不超过k堆果子合并，代价为总果子数，询问在代价不超过t的情况下，k的最小值。

思路

由于答案具有单调性，想到二分。

显然较大的参与合并次数应该少，考虑每次取最少的k堆果子合并。

然而仍然有问题

试手算

4 13

1 2 3 4

答案是3

为什么呢

可以先合并1，2，再合并3 3 4就好了。

所以当(n-1)%(k-1)>0时，应该先将(n-1)%(k-1)+1合并。

本题疯狂卡时，丧病。

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<queue>
 5 using namespace std;
 6 const int N=100005;
 7 int T,n,t,a[N],sm[N];
 8 priority_queue<int,vector<int>,greater<int> >q;
 9 bool check(int k)
10 {
11     while(!q.empty())
12         q.pop();
13     int cst=0,m=(n-1)/(k-1),mo=(n-1)%(k-1);
14     if(mo)
15     {
16         mo++;
17         cst+=sm[mo];
18         q.push(cst);
19     }
20     for(int i=mo+1;i<=n;i++)
21         q.push(a[i]);
22     for(int i=1;i<=m;i++)
23     {
24         int sum=0;
25         for(int j=1;j<=k;j++)
26         {
27             sum+=q.top();
28             q.pop();
29         }
30         cst+=sum;
31         if(cst>t)
32             return 0;
33         q.push(sum);
34     }
35     return 1;
36 }
37 int main()
38 {
39     scanf("%d",&T);
40     while(T--)
41     {
42         scanf("%d%d",&n,&t);
43         for(int i=1;i<=n;i++)
44             scanf("%d",&a[i]);
45         sort(a+1,a+n+1);
46         for(int i=1;i<=n;i++)
47             sm[i]=sm[i-1]+a[i];
48         int l=2,r=n,mid;
49         while(l<r)
50         {
51             mid=(l+r)/2;
52             if(check(mid))
53                 r=mid;
54             else
55                 l=mid+1;
56         }
57         if(n==1)
58             l=1;
59         printf("%d
",l);
60     }
61     return 0;
62 }