受标签影响的最大值-c语言解决

受标签影响的最大值-c语言解决

我们有一个 n 项的集合。给出两个整数数组 values 和 labels ，第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。

从 n 个元素中选择一个子集 s :

子集 s 的大小 小于或等于 numWanted 。
s 中 最多 有相同标签的 useLimit 项。

一个子集的 分数 是该子集的值之和。

返回子集 s 的最大 分数 。

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。

示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。

示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
输出：16
解释：选出的子集是第一项和第四项。

void B_sort(int* values,int valuesSize,int* labels,int low,int high){
   // printf("%d %d ",low,high);
    int pivat_v;
     int pivat_l;
     int i=low,j=high;
    
     if(low<high){
         pivat_v=values[low];
         pivat_l=labels[low];
     while(low<high){
         while(values[high]<pivat_v&&low<high){
            high--;
      
         }
      // printf("--%d %d ",low,high);
       if(low==high) break;
      
         values[low]=values[high];
          labels[low++]=labels[high];
         while(values[low]>pivat_v&&low<high){
             low++;
       
         }
         if(low==high) break;
        
        
         values[high]=values[low];
          labels[high--]=labels[low];
     }
     values[low]=pivat_v;
     labels[low]=pivat_l;


     B_sort(values,valuesSize,labels,i,low-1);
     B_sort(values,valuesSize,labels,low+1,j);
     }


}


int largestValsFromLabels(int* values, int valuesSize, int* labels, int labelsSize, int numWanted, int useLimit){
    int  label_r[100000];
    int i,j;
    int sum=0;
    int n=0;
    for(i=0;i<100000;i++){
        label_r[i]=0;
    }
     B_sort(values,valuesSize,labels,0,valuesSize-1);
     for(i=0;i<valuesSize;i++){
         printf("// %d ",values[i]);
          //printf("%d ",labels[i]);


     }

    for(j=0;j<valuesSize;j++){
        if(label_r[labels[j]]<useLimit){
            label_r[labels[j]]++;
            sum=sum+values[j];
            n++;
        }
        if(n==numWanted)break;
    }
    return sum;


}