[Codeforces 1130D2] Toy Train

[Codeforces 1130D2] Toy Train

Problem - D2 - Codeforces

문제 설명 : 

n개의 역이 있는 장난감 기차가 있다. 그리고 이 기차는 m개의 사탕을 옮겨야 한다. 각 사탕에는 출발역과 도착역의 정보가 주어지고 최종 목표는 모든 사탕들을 도착역으로 운반시켜야 한다. 기차에 실을 수 있는 사탕의 개수는 무제한이지만, 한 역에서 기차에 실을 수 있는 사탕은 최대 1개이다. 기차의 출발 지점이 1~n번 역일 때 각 역마다 사탕을 모두 운반하기 위한 최소 이동 횟수를 구하는 문제이다.

 

풀이 : 

(이 문제는 쉬운 버전이 있고, 어려운 버전이 있는데 어려운 버전을 기준으로 설명한다. 둘의 차이는 n,m의 크기이다.)

출발역과 도착역을 입력을 받을 때부터 거리를 미리 계산해 놓도록 하자. 만약 n->1이 되어 한 바퀴를 돌게 되면 n을 더해주어서 값을 보정해주어야 한다. 그 다음은 1~n동안 각 역에서 출발하는 경우마다 현재 지점(j)에서 시작 지점(i)간의 거리를 계산해주자. 운반해야 할 캔디가 여러 개라면, 처음에는 운반 거리가 긴 캔디를 먼저 옮기고 나중에 짧은 캔디를 옮겨야 거리 단축에서 유리하다. 따라서 계산한 거리 중에서 가장 짧은 거리 하나만 선택하면 된다. 나머지 사탕들은 그 전에 이미 운반이 완료되었기 때문이다.

 

주의할 점 : 

처음에 이 문제를 틀렸었는데 그 이유는 내가 한 가지를 단정하고 넘어갔기 때문이다. 그것은 바로 이동 거리는 무조건 사탕의 개수가 많은 역에서 결정된다라는 것이었는데 사실 반례가 있었다. n=10이고 출발 지점이 10일 때, (1,2),(1,3),(9,8)만 보더라도 사탕이 2개인 1번 역이 1개인 9번 역보다 더 적은 횟수를 차지한다. 그래서 출발 역의 개수와 상관 없이 모든 역을 다 조사해보아야 함을 알 수 있다.

 

배운 점 : 

-

 

코드 : 

#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<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
// #define SIZE
// #define IMP
// #define INF
// const int MOD=
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> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
const int SIZE=5009;


vector<int> v[SIZE],dist[SIZE];
int main(){
    int n,m;    scanf("%d %d",&n,&m);

    for(int i=1 ;i<=m ; i++){
        int a,b;    scanf("%d %d",&a,&b);
        v[a].push_back(b);
        dist[a].push_back((b+n-a)%n);
    }

    int max_cnt=0;

    for(int i=1 ; i<=n ; i++)
            sort(dist[i].begin(),dist[i].end());

    for(int i=1 ; i<=n ; i++){
        int ans=0;
        for(int j=1 ; j<=n ; j++){
            if(dist[j].size()==0) continue;
            int tmp=(j+n-i)%n;
            tmp+=dist[j][0];
            tmp+=n*(dist[j].size()-1);
            ans=max(ans,tmp);
        }
        printf("%d ",ans);
    }

    return 0;
}