[Codeforces 1041D] Glider

[Codeforces 1041D] Glider - 1700

문제 설명 : 

높이가 h인 공중에서 글라이더를 날린다. 글라이더를 날려 보내기 시작하는 지점은 상관없다. 기본적으로 글라이더는 낙하하면서 고도가 1미터 낮아질 때마다 앞으로 1미터씩 비행하는데, 상승기류가 존재하는 구간이 있어서 그 구간에서는 글라이더의 고도가 낮아지지 않으면서 앞으로 1미터씩 비행한다. 이때 글라이더가 비행을 시작한 시점부터 땅에 닿기까지 최대로 비행할 수 있는 거리를 구하는 문제이다.

풀이 :

두 가지 풀이가 있는데 하나는 이분탐색, 다른 하나는 투포인터이다. 처음에 내가 떠올린 풀이는 투포인터였는데 구현이 꼬여서 우선 이분탐색으로 푼 다음에 다시 투포인터로 풀었다. 문제에서 글라이더의 고도가 0이 되기 전까지는 계속 1미터씩 비행할 수 있으므로, 언제부터(어느 지점부터) 비행을 시작해야 오랫동안 날 수 있는지를 구해야한다. 단순 낙하하는 케이스의 경우 어느 지점에서든지 고도 1미터당 거리 1미터씩 비행하므로 이는 고려할 필요가 없다. 내가 신경써야 할 것은 상승기류 구간에서 최대한 오랫동안 비행하는 것이다. 즉 높이 h에서 낙하기 시작하면서 얼마나 길게 상승기류 구간을 지날 수 있는지가 관건이다. 

투포인터 풀이 :

(어떤 상승기류의 끝점~다음 상승기류의 시작점) 사이의 거리에서는 낙하할 수 밖에 없다. 그래서 먼저 상승기류간의 거리 차이들을 누적합 형태로 배열에 저장한다(=gap[]). 그리고 높이 h를 초과하지 않는 한도 내에서 방금 구한 거리 차이들을 넓혀나가면서(=gap[j]-gap[i]), 동시에 상승기류 구간의 길이도 같이 더한다(=cur_sum). 더이상 넓힐 수 없다면 그 동안 저장된 구간의 합의 최대값을 저장하기 위해 ans와 비교연산한다. 이 시행이 끝나고 나면 cur_sum에 dist[i]를 빼고 다음 구간인 [i+1]로 넘어가서 (가능하다면) 오른쪽 범위를 넓혀나간다.

이분탐색 풀이 : 

현재 지점에서 h의 거리 안에 속하면서 좌표가 가장 큰 상승기류의 구간을 찾는다. 그 지점까지의 구간 길이들의 합을 더해서 ans값과 비교하여 갱신한다.

주의할 점 : 

-

배울 점 : 

투포인터를 구현하는 부분은 아직 더 연습을 해야겠다.

코드 :

 

(투포인터 풀이)

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
 
inline void showAll(vector<int> &v,int NL_or_space=0){ 
    //0 is space(default), 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 200009;
 
pii arr[SIZE];
int gap[SIZE];
int dist[SIZE];
 
int main(){
    int n,h;    scanf("%d %d",&n,&h);
 
    for(int i=1 ; i<=n ; i++){
        int x1,x2;  scanf("%d %d",&x1,&x2);
        arr[i]={x1,x2};
        gap[i]=gap[i-1]+(arr[i].first-arr[i-1].second);
        dist[i]=x2-x1;
    }
 
    ll ans=0;
    ll cur_sum=0;
    for(int i=1,j=1 ; i<=n ; i++){
        while(gap[j]-gap[i] <h && j<=n){
            cur_sum+=dist[j];
            j++;
        }
 
        ans=max(ans,cur_sum);
        cur_sum-=dist[i];
    }
    
    ans+=h;
    printf("%lld\n",ans);
    return 0;
}
 

(이분탐색 풀이)

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
 
inline void showAll(vector<int> &v,int NL_or_space=0){ 
    //0 is space(default), 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 200009;
 
pii arr[SIZE];
int gap[SIZE],dist[SIZE];
ll gap_sum[SIZE],dist_sum[SIZE];
 
int main(){
    int n,h;    scanf("%d %d",&n,&h);
 
    for(int i=1 ; i<=n ; i++){
        int x1,x2;  scanf("%d %d",&x1,&x2);
        arr[i]={x1,x2};
        dist[i]=x2-x1;
        if(i==1) gap[i]=0;
        else gap[i]=x1-arr[i-1].second;
        dist_sum[i]=dist_sum[i-1]+dist[i];
        gap_sum[i]=gap_sum[i-1]+gap[i];
    }
 
    ll ans=0;
    for(int i=1 ; i<=n ; i++){
        int l=i-1,r=n+1,mid;
        ll find=gap_sum[i]+h;
        while(l+1<r){
            mid=(l+r)/2;
 
            if(gap_sum[mid]>=find)
                r=mid;
            else l=mid;
 
        }
        ans=max(ans,dist_sum[l]-dist_sum[i-1]);
    }
    ans+=h;
    printf("%lld\n",ans);
 
 
 
    return 0;
    
}