fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. Problem: Minimum Operations to Reduce Total Weight
  6.  
  7. You are given:
  8. - an integer n
  9. - an integer k
  10. - an array bags of length n where bags[i] represents the weight of the i-th bag
  11.  
  12. You want to make the total sum of all bag weights at most k.
  13.  
  14. In one operation, you can do exactly one of the following:
  15.  
  16. 1) Decrease the weight of any one bag by 1
  17.    Example: if bags[i] = 7, after one operation it can become 6
  18.  
  19. 2) Make one bag's weight equal to another bag's weight
  20.    Example: if bags[i] = 10 and bags[j] = 4, you may set bags[i] = bags[j], so bags[i] becomes 4
  21.  
  22. Your task is to find the minimum number of operations required to make:
  23. bags[0] + bags[1] + ... + bags[n-1] <= k
  24.  
  25. Important points:
  26. - Bag weights are allowed to become negative
  27. - You can perform any number of operations
  28. - Each decrease by 1 costs one operation
  29. - Each copy operation also costs one operation
  30.  
  31. ------------------------------------------------------------
  32.  
  33. Example:
  34. Input:
  35. n = 5
  36. k = 10
  37. bags = [5, 1, 3, 7, 9]
  38.  
  39. Output:
  40. minimum number of operations needed so that total sum <= 10
  41.  
  42. ------------------------------------------------------------
  43.  
  44. Idea used in this solution:
  45.  
  46. After sorting the array, the best strategy can be thought of like this:
  47. - reduce the smallest element to some value x
  48. - make some number of the largest elements equal to x
  49.  
  50. Why?
  51. Because copying a large value down to a smaller one is often much cheaper than decreasing it one by one.
  52.  
  53. So for every possible number of largest elements we decide to overwrite, we calculate:
  54. - what the smallest value x should be
  55. - how many decrement operations are needed
  56. - how many copy operations are needed
  57.  
  58. Then we take the minimum over all choices.
  59.  
  60. Time Complexity: O(n log n)
  61. Space Complexity: O(n)
  62. */
  63.  
  64. class Solution {
  65. private:
  66.     // Returns floor(a / b) for b > 0
  67.     long long floorDivide(long long a, long long b) {
  68.         if (a >= 0) return a / b;
  69.         return -((-a + b - 1) / b);
  70.     }
  71.  
  72. public:
  73.     long long minMovesToLimitWeight(int n, long long k, vector<long long>& bags) {
  74.         sort(bags.begin(), bags.end());
  75.  
  76.         long long totalSum = 0;
  77.         for (long long weight : bags) {
  78.             totalSum += weight;
  79.         }
  80.  
  81.         // If the sum is already within limit, no operation is needed
  82.         if (totalSum <= k) return 0;
  83.  
  84.         // prefix[i] = sum of first i elements
  85.         vector<long long> prefix(n + 1, 0);
  86.         for (int i = 0; i < n; i++) {
  87.             prefix[i + 1] = prefix[i] + bags[i];
  88.         }
  89.  
  90.         /*
  91.         Main idea:
  92.         Try taking the smallest element and reducing it to some value x.
  93.         Also try copying that x into the largest 'take' elements.
  94.  
  95.         Then:
  96.         - copy cost = take
  97.         - decrease cost = bags[0] - x
  98.         */
  99.  
  100.         long long answer = totalSum - k; // worst case: only use decrement operations
  101.  
  102.         for (int take = 0; take < n; take++) {
  103.  
  104.             // Sum of the largest 'take' elements
  105.             long long largestPart = prefix[n] - prefix[n - take];
  106.  
  107.             // Sum of elements that remain unchanged
  108.             long long fixedPart = totalSum - bags[0] - largestPart;
  109.  
  110.             /*
  111.             New total after changes:
  112.             fixedPart + (take + 1) * x
  113.  
  114.             We need:
  115.             fixedPart + (take + 1) * x <= k
  116.  
  117.             So:
  118.             x <= (k - fixedPart) / (take + 1)
  119.  
  120.             Since x may be negative, use floor division carefully.
  121.             */
  122.             long long allowedX = floorDivide(k - fixedPart, take + 1);
  123.  
  124.             // We can only decrease the smallest value, not increase it
  125.             long long finalSmallest = min(bags[0], allowedX);
  126.  
  127.             long long operations = take + (bags[0] - finalSmallest);
  128.  
  129.             answer = min(answer, operations);
  130.         }
  131.  
  132.         return answer;
  133.     }
  134. };
  135.  
  136. int main() {
  137.     Solution sol;
  138.  
  139.     vector<long long> bags = {5, 1, 3, 7, 9};
  140.  
  141.     cout << sol.minMovesToLimitWeight(5, 10, bags) << '\n';
  142.  
  143.     return 0;
  144. }
Success #stdin #stdout 0.01s 5340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/Pal4fa
language:
C++14 (gcc 8.3)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!