HDU 5884 （贪心）

problem sort

题目大意

　　有n个数组，每个数组有a[i]个元素，每次可以将至多k个数组合并为一个数组，所花费代价为这些数组的元素和。给定代价上限，求将所有数组合并为1个数组的最小k。

解题分析　　

　　二分k后就成了k叉哈夫曼树问题。

　　对于k叉哈夫曼树，可以利用所合并元素的权值单调性，用两个双端队列来实现。

　　另外，如果(n-1)%(k-1) != 0 , 则需要另外在补上(k-1) - (n-1)%(k-1)个0。

参考程序

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <string>

 #include <vector>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cassert>

 #include <iostream>

 #include <algorithm>

 #pragma comment(linker,"/STACK:102400000,102400000")

 using namespace std;

 #define N 100008

 #define M 50008

 #define LL long long

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define clr(x,v) memset(x,v,sizeof(x));

 #define bitcnt(x) __builtin_popcount(x)

 #define rep(x,y,z) for (int x=y;x<=z;x++)

 #define repd(x,y,z) for (int x=y;x>=z;x--)

 const int mo  = ;

 const int inf = 0x3f3f3f3f;

 const int INF = ;

 /**************************************************************************/ 

 int T;

 int n,limit;

 int a[N*],b[N*],c[N*];

 int check(int k)

 {

     //printf("%d\n",k );

     int tmp=((k-)-(n-) % (k-)) % (k-);

     int m=n+tmp;

     rep(i,,tmp) b[i]=;

     rep(i,tmp+,m) b[i]=a[i-tmp];

     LL s=;

     int i=,l=,r=,op=,sum=;

     while (i<=m)

     {

         if (l>r || b[i]<=c[l])

         {

             op++;

             sum+=b[i];

             i++;

         }

         else

         {

             op++;

             sum+=c[l];

             l++;

         }

         if (op==k)

         {

             s+=sum;

             c[++r]=sum;

             op=sum=;

         }

     }

     while (l<=r)

     {

         op++;

         sum+=c[l];

         l++;

         if (op==k)

         {

             s+=sum;

             c[++r]=sum;

             op=sum=;

         }

     }

     //rep(i,1,m)  printf("%d ",b[i]); printf("\n");

     //rep(i,1,r)  printf("%d ",c[i]); printf("\n");

     if (op!=) s+=sum;

     //printf("%lld\n",s );

     return s<=limit;

 }

 int cmp(int x,int y)

 {

     return x>y;

 }

 int main()

 {

     scanf("%d",&T);

     while (T--)

     {

         scanf("%d%d",&n,&limit);

         rep(i,,n) scanf("%d",&a[i]);

         sort(a+,a+n+);

         int l=,r=n,mid,res;

         while (l<=r)

         {

             mid=(l+r)/;

             if (check(mid))

             {

                 res=mid;

                 r=mid-;

             }

             else l=mid+;

         }

         printf("%d\n",res);

     }

 }

巴特西

HDU 5884 （贪心）

最新文章

热门文章