Untitled
raw download clone
C
views 64
,
size 1706 b
#include<stdio.h>//i個物品最少要花多少錢

int cmp(const void *a,const void *b)
{
     int *va=(const int*)a;
     int *vb=(const int*)b;
     return *va-*vb;
}

/*int BS(int *pre,int p,int n)
{
     int left=1,right=n+1,ans=0;
     while(left<right)
     {
          int mid=(left+right)/2;
          if(p>=pre[mid])
          {
               left=mid;
               ans=mid;
               if(right==left+1)return mid;
          }
          else if(p<pre[mid])
          {
               right=mid-1;
          }
          //else return mid;
     }
     return (left+right)/2;
}*/

int main(void)
{
     int t,n,money,k,i,j;
     scanf("%d\n",&t);
     while(t--)
     {
          int *a,*pre,num=0,max=0;

          scanf("%d%d%d\n",&n,&money,&k);
          a=(int*)malloc((n+1)*sizeof(int));
          pre=(int*)malloc((n+1)*sizeof(int));
          for(i=1;i<=n;i++)
          {
               scanf("%d",a+i);
          }
          qsort(a+1,n,sizeof(int),cmp);
          for(i=0;i<=n;i++)
          {
               pre[i]=0;
          }
          for(i=1;i<k;i++)
          {
               pre[i]+=(a[i]+pre[i-1]);
               //printf("%d ",pre[i]);
          }
          for(i=k;i<=n;i++)
          {
               pre[i]=a[i]+pre[i-k];
               //printf("%d ",pre[i]);
          }
          if(pre[1]>money)printf("0\n");
          else
          {
               int ans=0;
               for(i=1;i<=n;i++)
               {
                    if(money>=pre[i])ans=i;
               }
               printf("%d\n",ans);
          }

          free(a);
          free(pre);
     }
     return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.