Advertisement
Guest User

Untitled

a guest
Oct 21st, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.37 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. typedef struct {
  8.     int pos;
  9.     int len;
  10. } Boat;
  11.  
  12. bool cmp(const Boat & a, const Boat & b){
  13.     return a.pos < b.pos;
  14. }
  15.  
  16. void solve(){
  17.     int n;
  18.     cin >> n;
  19.     // trivial cases for n=1 and n=2
  20.     if(n < 3){
  21.         cout << n << endl;
  22.         return;
  23.     }
  24.  
  25.     vector<Boat> boatsNein;
  26.     for(int i = 0; i < n; ++i){
  27.         Boat b;
  28.         cin >> b.len;
  29.         cin >> b.pos;
  30.         boats[i] = b;
  31.     }
  32.     // sort boats by their ring position from left to right
  33.     sort(boats.begin(), boats.end(), cmp);
  34.  
  35.     //the rightmost boat on the illustrations is the one being considered to add
  36.  
  37.     // the first boat can always fit like this:
  38.     //|=========|~~~~~~~~~~~~~~~~
  39.     //          ^
  40.     int cnt = 1;
  41.     int last_ship_right_end = boats[0].pos;
  42.     int last_ship_left_end = boats[0].pos - boats[0].len;
  43.  
  44.     for(int i = 1; i < n-1; ++i){
  45.         // if the boat can fit to the gap between the right end of the previous boat and the ring, do it:
  46.         //|========|~~~|==========|
  47.         //   ^                    ^
  48.         if(last_ship_right_end <= boats[i].pos - boats[i].len){
  49.             cnt++;
  50.             last_ship_right_end = boats[i].pos;
  51.             last_ship_left_end = boats[i].pos - boats[i].len;
  52.         }
  53.         else{
  54.             // if the boat can be tied to its ring, even though it will extend to the right, do it:
  55.             // |=======|=============|
  56.             //     ^          ^
  57.             if(last_ship_right_end <= boats[i].pos){
  58.                 cnt++;
  59.                 last_ship_left_end = last_ship_right_end;
  60.                 last_ship_right_end = last_ship_left_end + boats[i].len;
  61.             }
  62.             else{
  63.                 // if the boat cannot be tied to its ring because it is occupied by the previous boat,
  64.                 // but can replace it so that its right end is tied to the ring and the original boat's
  65.                 // right end was further to the right than the ring, do the replace:
  66.                 // BEFORE
  67.                 // |==========================|
  68.                 //       ^              ^
  69.                 // AFTER
  70.                 // ~~~~~~~~~~~~|========|~~~~~~
  71.                 //       ^              ^
  72.                 if(boats[i].pos - boats[i].len >= last_ship_left_end && last_ship_right_end > boats[i].pos){
  73.                     last_ship_left_end = boats[i].pos - boats[i].len;
  74.                     last_ship_right_end = boats[i].pos;
  75.                 }
  76.  
  77.                 // same story as before, but the boat extends to the right of its ring, but not that much
  78.                 // as the previous one
  79.                 // BEFORE
  80.                 // |==========================|
  81.                 //       ^              ^
  82.                 // AFTER
  83.                 // |=======================|~~~
  84.                 //       ^              ^
  85.                 else if(last_ship_left_end + boats[i].len < last_ship_right_end){
  86.                     last_ship_right_end = last_ship_left_end + boats[i].len;
  87.                 }
  88.             }
  89.         }
  90.     }
  91.  
  92.     // the last boat can always extend to the right provided its ring is free
  93.     if(last_ship_right_end <= boats[n-1].pos){
  94.         cnt++;
  95.     }
  96.  
  97.     cout << cnt << endl;
  98. }
  99.  
  100. int main(){
  101.     ios_base::sync_with_stdio(0);
  102.     int tc;
  103.     cin >> tc;
  104.     while(tc--){solve();}
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement