2333. 最小差值平方和-排序加二分查找，力扣c语言题解

2333. 最小差值平方和-排序加二分查找，力扣c语言题解

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度为 n 。

数组 nums1 和 nums2 的 差值平方和 定义为所有满足 0 <= i < n 的 (nums1[i] - nums2[i])2 之和。

同时给你两个正整数 k1 和 k2 。你可以将 nums1 中的任意元素 +1 或者 -1 至多 k1 次。类似的，你可以将 nums2 中的任意元素 +1 或者 -1 至多 k2 次。

请你返回修改数组 nums1 至多 k1 次且修改数组 nums2 至多 k2 次后的最小 差值平方和 。

注意：你可以将数组中的元素变成 负 整数。

示例 1：

输入：nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
输出：579
解释：nums1 和 nums2 中的元素不能修改，因为 k1 = 0 和 k2 = 0 。
差值平方和为：(1 - 2)2 + (2 - 10)2 + (3 - 20)2 + (4 - 19)2 = 579 。

示例 2：

输入：nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1
输出：43
解释：一种得到最小差值平方和的方式为：

• 将 nums1[0] 增加一次。
• 将 nums2[2] 增加一次。
  最小差值平方和为：
  (2 - 5)2 + (4 - 8)2 + (10 - 7)2 + (12 - 9)2 = 43 。
  注意，也有其他方式可以得到最小差值平方和，但没有得到比 43 更小答案的方案。
  对于这一题，我给出两种常规解法，但是时间复杂度都无法通过;

long long minSumSquareDiff(int* nums1, int nums1Size, int* nums2, int nums2Size, int k1, int k2){
    int r[nums1Size];
    int i,j;
    for(i=0;i<nums1Size;i++){
        r[i]=abs(nums1[i]-nums2[i]);
    }
    int n=k1+k2;
    while(n!=0){
       
        int max=r[0];
        int index=0;
        
        for(i=1;i<nums1Size;i++){
            if(r[i]>max){
                max=r[i];
               index=i;
            }
        }
        if(max==0){
            return 0;
        }
        r[index]--;


        n--;
    }
    long long sum=0;
     for(i=0;i<nums1Size;i++){
      sum=sum+r[i]*r[i];
    }
    return sum;


}

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

int cmp(const void *a,const void *b){
    return  *(int *)b-*(int *)a;
}
int f(int *r,int n,int nums1Size){
    int max=r[0];  
    int min, j=1;
      if(max==0){
       return 0;
   }
    while(r[j]==max){
        j++;
         if(j==nums1Size){
             break;
         }
    }
    if(j==nums1Size){
        min=0;
    }
   else{
       min=r[j];
   }
   //printf("dfa %d  %d ",min,max);
 
  
    int sub=max-min;
    if((j-0)*sub<=n){
        for(int k=0;k<j;k++){
            r[k]=min;
        }
        n=n-sub*(j-0);

    }
    else{
      int s=n/(j-0);
        for(int k=0;k<j;k++){
            r[k]=r[k]-s;
        }
        n=n-s*(j-0);
          for(int k=0;k<n;k++){
            r[k]=r[k]-1;
        }
        return 0;



    }
    return n;
}


long long minSumSquareDiff(int* nums1, int nums1Size, int* nums2, int nums2Size, int k1, int k2){
    int *r=(int *)malloc(sizeof(int)*nums1Size);
    int i,j;
    long long  sumt=0;
    for(i=0;i<nums1Size;i++){
        r[i]=abs(nums1[i]-nums2[i]);
        sumt=sumt+r[i];
    }
   
    qsort(r,nums1Size,sizeof(int),cmp);
    //    for(i=0;i
    //   printf("%d ",r[i]);
    // }
    int n=k1+k2;
     printf("||%d  %d ",sumt,n);
     if(sumt<n){
    //     printf("dfas");
         return 0;
     }
    while(n!=0){
        n=f(r,n,nums1Size);
     //   printf("--%d ",n);
       
     
    }
  
    long long sum=0;
     for(i=0;i<nums1Size;i++){
        long long a=r[i];
      sum=sum+a*a;
    }
    return sum;


}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

最终解题代码如下，排序加二分法：
二分法去做这题，可以解决，但是，细节处理较多，目前力扣平台也没有题解，下面是我的代码，感兴趣的，可以参考一下：

long long cmp(const void *a,const void *b){
    return  *(long long *)b-*(long long *)a;
}
long long f(long long *r, long long n, long long nums1Size){
    long long max=r[0];  
    long long min, j=1;
      if(max==0){
       return 0;
   }
    while(r[j]==max){
        j++;
         if(j==nums1Size){
             break;
         }
    }
    if(j==nums1Size){
        min=0;
    }
   else{
       min=r[j];
   }
   //printf("dfa %d  %d ",min,max);
 
  
    long long sub=max-min;
    if((j-0)*sub<=n){
        for(long long k=0;k<j;k++){
            r[k]=min;
        }
        n=n-sub*(j-0);

    }
    else{
      long long s=n/(j-0);
        for(long long k=0;k<j;k++){
            r[k]=r[k]-s;
        }
        n=n-s*(j-0);
          for(long long k=0;k<n;k++){
            r[k]=r[k]-1;
        }
        return 0;



    }
    return n;
}
long long sumf(long long *r, long long index){
    long long i=0;
    long long sum=0;
    for(;i<index;i++){
        sum=sum+r[i]-r[index];

    }
    return sum;
}
long long subf(long long *r, long long index){
     long long i=0;
 long long su=0;
    for(;i<index;i++){
        su=r[i]-r[index]+su;
      r[i]=r[index];

    }
    return su;

}
long long find(long long *r, long long low, long long high, long long n){
    if(r[low]==r[high]){
        return -1;
    }
    
    while(low<high){
        long long p=(low+high)/2;
        long long su=sumf(r,p);
        if(su==n){
            return p;
        }
        if(su>n){
           high=p-1;
        }
        else{
            low=p+1;
            
        }
    }

        return high;
  
}
void f3(long long *r, long long index, long long n){
    long long sub=n/index;
    long long f=n-index*sub;
    
    for(long long i=0;i<index;i++){

        if(i<f){
            r[i]=r[i]-sub-1;
        }
        else{
            r[i]=r[i]-sub;
        }
    }
}



long long minSumSquareDiff(int* nums1, int nums1Size, int* nums2, int nums2Size, int k1, int k2){
    long long *r=(long long *)malloc(sizeof(long long)*nums1Size);
    long long i,j;
    long long  sumt=0;
    for(i=0;i<nums1Size;i++){
        r[i]=abs(nums1[i]-nums2[i]);
        sumt=sumt+r[i];
    }
   
    qsort(r,nums1Size,sizeof(long long),cmp);
   
    long long n=k1+k2;
    
     if(sumt<n){
    //     printf("dfas");
         return 0;
     }
     

     if(n==0){
         long long sum=0;
           for(long long i=0;i<nums1Size;i++){
        
      sum=sum+r[i]*r[i];
    }
    return sum;


     }
 //  printf("defsa");
 long long p=0;
     while(n!=0){
         
    //       for(i=0;i
    //        printf("%d ",r[i]);
    //    }
        // p++;
        // if(p==100){break;}
    
         long long index=find(r,0,nums1Size-1,n);
        
        // printf("%d ",sumf(r,index));
 //    printf("index1 %d n %d --",index,n);
  //  printf("++%d ",index);

   if(sumf(r,index-1)!=0&&sumf(r,index-1)<=n&&sumf(r,index)>n){
         n=n-subf(r, index-1);
     //     printf("index %d n %d --",index,n);
         continue;

   }
         if(sumf(r,index)>n&&sumf(r,index-1)<=n){
             f3(r,index,n);
             n=0;
         }
         else{
             if(index==-1){
                 if(nums1Size*r[0]<=n){
                     return 0;
                 }
                 else{
                        f3(r,nums1Size,n);
                        n=0;

                 }
                

             }
             else{
                 if(r[index]==r[0]&&sumf(r,index+1)>=n){
                       f3(r,index+1,n);
                         break;

                 }
                
                       n=n-subf(r, index);

                
                

             }
            

        
            

         }
       
        
       
     }
       
  
   

     
   
        
      
    //     while(n!=0){
    //     n=f(r,n,nums1Size);
    //  //  printf("--%d ",n);
       
     
    // }



     long long sum=0;
  
     for(i=0;i<nums1Size;i++){
      
      sum=sum+r[i]*r[i];
    }
    return sum;


}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226