2333 added.

liuyubobobo · liuyubobobo · commit 394b4e17886e · 2022-07-10T15:14:44.000-07:00
diff --git a/2001-2500/2333-Minimum-Sum-of-Squared-Difference/cpp-2333/CMakeLists.txt b/2001-2500/2333-Minimum-Sum-of-Squared-Difference/cpp-2333/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(C)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(C main.cpp)
diff --git a/2001-2500/2333-Minimum-Sum-of-Squared-Difference/cpp-2333/main.cpp b/2001-2500/2333-Minimum-Sum-of-Squared-Difference/cpp-2333/main.cpp
@@ -0,0 +1,76 @@
+/// Source : https://leetcode.com/problems/minimum-sum-of-squared-difference/
+/// Author : liuyubobobo
+/// Time   : 2022-07-10
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+
+/// Soring and Greedy
+/// Time Complexity: O(nlogn)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    long long minSumSquareDiff(vector<int>& nums1, vector<int>& nums2, int k1, int k2) {
+
+        int n = nums1.size();
+        vector<long long> d(n);
+        for(int i = 0; i < n; i ++) d[i] = abs(nums1[i] - nums2[i]);
+
+        sort(d.begin(), d.end(), greater<int>());
+        d.push_back(0);
+        n ++;
+
+        long long k = k1 + k2;
+
+        long long pre = d[0];
+        int i;
+        for(i = 1; i < n; i ++){
+            long long cur = d[i];
+            long long diff = pre - cur;
+            if(diff * i <= k){
+                k -= diff * i;
+                pre = cur;
+            }
+            else{
+                break;
+            }
+        }
+
+        if(i < n){
+            for(int j = 0; j < i; j ++) d[j] = pre;
+
+            for(int j = 0; j < i; j ++){
+                d[j] -= k / i;
+                if(j < k % i) d[j] --;
+            }
+        }
+        else return 0;
+
+        long long res = 0;
+        for(int i = 0; i < n; i ++)
+            res += d[i] * d[i];
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<int> nums11 = {1, 2, 3, 4}, nums12 = {2, 10, 20, 19};
+    cout << Solution().minSumSquareDiff(nums11, nums12, 0, 0) << '\n';
+    // 579
+
+    vector<int> nums21 = {1, 4, 10, 12}, nums22 = {5, 8, 6, 9};
+    cout << Solution().minSumSquareDiff(nums21, nums22, 1, 1) << '\n';
+    // 43
+
+    vector<int> nums31 = {19, 18, 19, 18, 18, 19, 19}, nums32 = {1, 0, 1, 0, 0, 1, 1};
+    cout << Solution().minSumSquareDiff(nums31, nums32, 10, 33) << '\n';
+    // 985
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -2176,6 +2176,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 2327 | [Number of People Aware of a Secret](https://leetcode.com/problems/number-of-people-aware-of-a-secret/) | [无] | [C++](2001-2500/2327-Number-of-People-Aware-of-a-Secret/cpp-2327/) | | |
 | 2328 | [Number of Increasing Paths in a Grid](https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/) | [无] | [C++](2001-2500/2328-Number-of-Increasing-Paths-in-a-Grid/cpp-2328/) | | |
 | | | | | | |
+| 2333 | [Minimum Sum of Squared Difference](https://leetcode.com/problems/minimum-sum-of-squared-difference/) | [无] | [C++](2001-2500/2333-Minimum-Sum-of-Squared-Difference/cpp-2333/) | | |
 | 2334 | [Subarray With Elements Greater Than Varying Threshold](https://leetcode.com/problems/subarray-with-elements-greater-than-varying-threshold/) | [无] | [C++](2001-2500/2334-Subarray-With-Elements-Greater-Than-Varying-Threshold/cpp-2334/) | | |
 | 2335 | [Minimum Amount of Time to Fill Cups](https://leetcode.com/problems/minimum-amount-of-time-to-fill-cups/) | [无] | [C++](2001-2500/2335-Minimum-Amount-of-Time-to-Fill-Cups/cpp-2335/) | | |
 | 2336 | [Smallest Number in Infinite Set](https://leetcode.com/problems/smallest-number-in-infinite-set/) | [无] | [C++](2001-2500/2336-Smallest-Number-in-Infinite-Set/cpp-2336/) | | |
