2994: 장애물 경기

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2262&sca=99&sfl=wr_subject&stx=%EC%9E%A5%EC%95%A0%EB%AC%BC+%EA%B2%BD%EA%B8%B0 

JUNGOL

물론 백준에도 이 문제가 있다. (문제번호 13303)

KOI 2016 초등부 4번 문제로 뇌빼고 풀면 잘 풀리는 문제이다. 참고로 뇌를 사용해서 풀면 더 어렵다.

간단하게 상황을 구현하고, 이때 조금만 생각하면 알 수 있듯이 자동으로 정렬이 되는 set을 이용하며, 각 장애물에 대해 위 아래 둘 중 무조건 한곳으로만 빠져나간다는 사실로 부터 각 장애물 마다 두 가지 경우에서의 최소값만 insert 해주면 된다.

 

아래는 코드이다.

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pll;
pair<ll,pll>A[100003];
set<pll>sp;
int main(){
    int N;ll x0,y0;
    scanf("%d%lld%lld",&N,&y0,&x0);
    for(int i=0;i<N;i++)scanf("%lld%lld%lld",&A[i].x,&A[i].y.x,&A[i].y.y);
    sort(A,A+N);
    sp.insert(pll(y0,0));
    for(int i=0;i<N;i++){
        set<pll>::iterator it=sp.lower_bound(pll(A[i].y.x,-1));
        vector<pll>vp;
        if(it->x<A[i].y.x)continue;
        while(it->x<=A[i].y.y){
            vp.push_back(*it);
            it++;
            if(it==sp.end())break;
        }
        ll t=9e18,b=9e18;
        if(vp.size()<=0)continue;
        for(int j=0;j<(int)vp.size();j++){
            t=min(t,vp[j].y+abs(vp[j].x-A[i].y.y));
            b=min(b,vp[j].y+abs(vp[j].x-A[i].y.x));
            sp.erase(vp[j]);
        }
        sp.insert(pll(A[i].y.y,t));
        sp.insert(pll(A[i].y.x,b));
    }
    set<pll>::iterator it;
    ll ans=9e18;
    vector<ll>pr;
    for(it=sp.begin();it!=sp.end();it++)ans=min(ans,it->y);
    for(it=sp.begin();it!=sp.end();it++)if(ans==it->y)pr.push_back(it->x);
    printf("%lld\n%d ",ans+x0,(int)pr.size());
    for(int i=0;i<(int)pr.size();i++)printf("%lld ",pr[i]);
    return 0;
}