paradox64ce

Greedy filling

Jun 19th, 2021
667
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool check(int k, int N, int W, vector<int> w){
  2.     // multiset<int> st;
  3.     // for(auto x:w){
  4.     //     st.insert(x);
  5.     // }  
  6.    
  7.     vector<int> boxes(k, W);
  8.     vector<int> taken(N, false);
  9.    
  10.     int box = 0;
  11.    
  12.     while(box<k){
  13.         bool flag = 0;
  14.         bool flag2 = 1;
  15.         for(int i = N-1;i>=0;i--){
  16.             if(!taken[i] && w[i]<=boxes[box]){
  17.                 boxes[box]-=w[i];
  18.                 taken[i] = 1;
  19.                 flag = 1;
  20.             }
  21.         }
  22.        
  23.         if(!flag){
  24.             box++;
  25.         }
  26.        
  27.         for(int i = 0;i<N;i++){
  28.             if(!taken[i]){
  29.             flag2 = false;
  30.         }
  31.            
  32.         if(flag2){
  33.             break;
  34.         }
  35.     }
  36.        
  37.     }
  38.    
  39.     for(int i = 0;i<N;i++){
  40.         if(!taken[i]){
  41.             return false;
  42.         }
  43.     }
  44.    
  45.     return true;
  46. }
  47.  
  48. int get_minimum_parcels(int N, int W, vector<int> w) {
  49.     // Write your code here. Complete this function to return the minimum number of parcels required by Michael.
  50.     sort(w.begin(), w.end());
  51.    
  52.     int l = 1, r = N, ans = N;
  53.     while(l<=r){
  54.         int m = (l+r)/2;
  55.         if(check(m, N, W, w)){
  56.             ans = m;
  57.             r = m - 1;
  58.         }else{
  59.             l = m + 1;
  60.         }
  61.     }
  62.     return ans;
  63. }
RAW Paste Data