• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Oct 21st, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top