2171. 拿出最少数目的魔法豆-快速排序+前缀和

2171. 拿出最少数目的魔法豆-快速排序+前缀和

给你一个 正 整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少 还有 一颗 魔法豆的袋子）魔法豆的数目 相等 。一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。

请你返回你需要拿出魔法豆的 最少数目。

示例 1：

输入：beans = [4,1,6,5]
输出：4
解释：

• 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,6,5]
• 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,5]
• 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
  剩下袋子中魔法豆的数目为：[4,0,4,4]
  总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
  没有比取出 4 个魔法豆更少的方案。

示例 2：

输入：beans = [2,10,3,2]
输出：7
解释：

• 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,2]
• 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,3,0]
• 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
  剩下袋子中魔法豆的数目为：[0,10,0,0]
  总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
  没有比取出 7 个魔法豆更少的方案。

一开始对于这个题目，博主想的使用二分查找的方法去做的，代码写到一半发现不行，才意识到，二分查找问题的序列必须是单调的，也是有了一个大的收获，解题代码如下：

void quick(int *a,int low,int high){
    if(low<high){
        int l=low,h=high,p=a[low];
        while(low<high){
            while(low<high&&a[high]>=p){
                high--;

            }
            a[low]=a[high];
            while(low<high&&a[low]<=p){
                low++;
            }
            a[high]=a[low];
        }
        a[low]=p;
        quick(a,l,low-1);
        quick(a,low+1,h);
    }
}
int cmp(const void* a, const void* b)
 {
     return *(int*)a - *(int*)b;
 }
long long minimumRemoval(int* beans, int beansSize){
   // quick(beans,0,beansSize-1);
     qsort(beans, beansSize, sizeof(int), cmp);
    long long sum=0;
    long long presum[beansSize];
    presum[0]=beans[0];
    for(int i=0;i<beansSize;i++){
        sum=sum+beans[i];
        if(i>0){
            presum[i]=presum[i-1]+beans[i];
        }
    }
    if(beans[0]==beans[beansSize-1]){
        return 0;
    }
    long long min=sum-beansSize*(long long)beans[0];
    int pre=beans[0];
    int index_pre=0;
    for(int i=1;i<beansSize;i++){
        if(beans[i]!=pre){
            pre=beans[i];
         long long sum_t=0;
        //  for(int j=0;j
        //      if(beans[j]
        //          sum_t=sum_t+beans[j];
        //      }
        //  }
   
         sum_t=sum-presum[i]-(beansSize-i-1)*(long long)beans[i]+presum[i-1];
         min=fmin(min,sum_t);
         index_pre=i;

        }
      

    }
    return min;

   

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65