我们有一个 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;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)