Sort(hdu5884)

Sort

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1038 Accepted Submission(s): 231

Problem Description

Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.
Alice will give Bob

Input

The first line of input contains an integer

Output

For each test cases, output the smallest

Sample Input

1 5 25 1 2 3 4 5

Sample Output

思路：二分+哈夫曼；

首先二分枚举k，然后关键就是check的时候，首先看一组数据：12345，当k为3的时候，按照如果我们取的话会得到21，然后再看k=4，我们的设想肯定是递减的，但是，如果我们开始就取4个的答案为25，所以这样二分就不行，但是是我们的取法不对，我们应该保证后面的大的数字竟量只取1次，那么最后k-1个数肯定被一次加完，不会有剩余，那么N个数如果从开始能选k个，那么剩下的肯定要是k-1的倍数，那么当剩下的不是k-1的倍数，我们要在前面添加0，个数就是k-1-（N-1）%（k-1）；这样就可以保证最优，也就单调了。

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<string.h>
  4 #include<iostream>
  5 #include<queue>
  6 #include<stdlib.h>
  7 #include<math.h>
  8 #include<set>
  9 using namespace std;
 10 typedef long long LL;
 11 queue<int>que1;
 12 queue<int>que2;
 13 LL ans[100005];
 14 bool check(int mid,int N,LL T);
 15 int main(void)
 16 {
 17     int n;
 18     scanf("%d",&n);
 19     while(n--)
 20     {
 21         int N;
 22         LL T;
 23         scanf("%d %lld",&N,&T);
 24         for(int i = 0; i < N; i++)
 25         {
 26             scanf("%lld",&ans[i]);
 27         }
 28         sort(ans,ans+N);
 29         int id = 1;
 30         int l = 2;
 31         int r = N;
 32         while(l<=r)
 33         {
 34             int mid = (l+r)/2;
 35             if(check(mid,N,T))
 36             {
 37                 r = mid-1;
 38                 id = mid;
 39             }
 40             else l = mid+1;
 41         }
 42         printf("%d
",id);
 43     }
 44     return 0;
 45 }
 46 bool check(int mid,int N,LL T)
 47 {
 48     LL ask = 0;
 49     while(!que1.empty())
 50     {
 51         que1.pop();
 52     }
 53     while(!que2.empty())
 54     {
 55         que2.pop();
 56     }
 57     int x = (N-1)%(mid - 1);
 58     if(x!=0)
 59     {
 60         x = (mid-1-x)%(mid-1);
 61         while(x)
 62         {
 63             que1.push(0);
 64             x--;
 65         }
 66     }
 67     for(int i = 0; i < N ; i++)
 68     {
 69         que1.push(ans[i]);
 70         ask-=ans[i];
 71     }
 72     while(true)
 73     {
 74         LL sum = 0;
 75         int c = mid;
 76         while(c)
 77         {
 78             int flag = 0;
 79             if(!que1.empty()&&!que2.empty())
 80             {
 81                 int t = que1.front();
 82                 int tt = que2.front();
 83                 if(t<=tt)
 84                 {
 85                     que1.pop();
 86                 }
 87                 else
 88                 {
 89                     t = tt;
 90                     que2.pop();
 91                 }
 92                 sum+=t;
 93                 c--;
 94                 flag = 1;
 95             }
 96             else if(!que1.empty())
 97             {
 98                 int t = que1.front();
 99                 que1.pop();
100                 sum+=t;
101                 c--;
102                 flag = 1;
103             }
104             else if(!que2.empty())
105             {
106                 int t = que2.front();
107                 que2.pop();
108                 sum+=t;
109                 c--;
110                 flag = 1;
111             }
112             if(!flag)
113                 break;
114         }
115         que2.push(sum);
116         ask += sum;
117         if(c>0)break;
118     }
119     if(ask > T)
120         return false;
121     else return true;
122 }

油！油！you@