Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef struct {
- int pos;
- int len;
- } Boat;
- bool cmp(const Boat & a, const Boat & b){
- return a.pos < b.pos;
- }
- void solve(){
- int n;
- cin >> n;
- // trivial cases for n=1 and n=2
- if(n < 3){
- cout << n << endl;
- return;
- }
- vector<Boat> boatsNein;
- for(int i = 0; i < n; ++i){
- Boat b;
- cin >> b.len;
- cin >> b.pos;
- boats[i] = b;
- }
- // sort boats by their ring position from left to right
- sort(boats.begin(), boats.end(), cmp);
- //the rightmost boat on the illustrations is the one being considered to add
- // the first boat can always fit like this:
- //|=========|~~~~~~~~~~~~~~~~
- // ^
- int cnt = 1;
- int last_ship_right_end = boats[0].pos;
- int last_ship_left_end = boats[0].pos - boats[0].len;
- for(int i = 1; i < n-1; ++i){
- // if the boat can fit to the gap between the right end of the previous boat and the ring, do it:
- //|========|~~~|==========|
- // ^ ^
- if(last_ship_right_end <= boats[i].pos - boats[i].len){
- cnt++;
- last_ship_right_end = boats[i].pos;
- last_ship_left_end = boats[i].pos - boats[i].len;
- }
- else{
- // if the boat can be tied to its ring, even though it will extend to the right, do it:
- // |=======|=============|
- // ^ ^
- if(last_ship_right_end <= boats[i].pos){
- cnt++;
- last_ship_left_end = last_ship_right_end;
- last_ship_right_end = last_ship_left_end + boats[i].len;
- }
- else{
- // if the boat cannot be tied to its ring because it is occupied by the previous boat,
- // but can replace it so that its right end is tied to the ring and the original boat's
- // right end was further to the right than the ring, do the replace:
- // BEFORE
- // |==========================|
- // ^ ^
- // AFTER
- // ~~~~~~~~~~~~|========|~~~~~~
- // ^ ^
- if(boats[i].pos - boats[i].len >= last_ship_left_end && last_ship_right_end > boats[i].pos){
- last_ship_left_end = boats[i].pos - boats[i].len;
- last_ship_right_end = boats[i].pos;
- }
- // same story as before, but the boat extends to the right of its ring, but not that much
- // as the previous one
- // BEFORE
- // |==========================|
- // ^ ^
- // AFTER
- // |=======================|~~~
- // ^ ^
- else if(last_ship_left_end + boats[i].len < last_ship_right_end){
- last_ship_right_end = last_ship_left_end + boats[i].len;
- }
- }
- }
- }
- // the last boat can always extend to the right provided its ring is free
- if(last_ship_right_end <= boats[n-1].pos){
- cnt++;
- }
- cout << cnt << endl;
- }
- int main(){
- ios_base::sync_with_stdio(0);
- int tc;
- cin >> tc;
- while(tc--){solve();}
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement