josiftepe

Untitled

Oct 17th, 2020
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <sstream>
  7. #include <cstdio>
  8. #include <algorithm>
  9. #include <stack>
  10. #include <queue>
  11. #include <cmath>
  12. #include <iomanip>
  13. #include <fstream>
  14. using namespace std;
  15.  
  16. int main() {
  17.     ios_base::sync_with_stdio(false);
  18.     int n, k;
  19.     cin >> n >> k;
  20.     vector<int> v(n);
  21.     for(int i = 0; i < n; ++i) {
  22.         cin >> v[i];
  23.     }
  24.     sort(v.begin(), v.end());
  25.     int ret = 0;
  26.     for(int i = 0; i < (int) v.size(); ++i) {
  27.         // for each i find the biggest number. such that their sum does not exceed x
  28.         int left_bound = i + 1;
  29.         int right_bound = (int) v.size() - 1;
  30.         int it = -1;
  31.         while(left_bound <= right_bound) {
  32.             int middle = (left_bound + right_bound) / 2;
  33.             if(v[middle] + v[i] <= k) {
  34.                 left_bound = middle + 1;
  35.                 it  = middle;
  36.             }
  37.             else {
  38.                 right_bound = middle - 1;
  39.             }
  40.         }
  41.         if(it != -1) {
  42. //            cout << v[i] << " " << v[it] << endl;
  43.             v.erase(v.begin() + it);
  44.             //erase(begin iterator, end iterator)
  45.             //erase(specific iterator)
  46.         }
  47.         ++ret;
  48.     }
  49.     cout << ret << endl;
  50.  
  51. }
  52. /*4 10
  53.   1, 3, 7, 9
  54.  
  55.  
  56. */
  57.  
Advertisement
Add Comment
Please, Sign In to add comment