[UVA 10881] 전형 적 인 시 뮬 레이 션 문제

제목 링크: http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=25979
제목: 길이 L 센티미터 의 나무 막대기 에 n 마리 의 개미 가 있 는데 개미 마다 시작 하 는 위치 와 기어 가 는 방향 이 있 고 속 도 는 1 이다. 개미 두 마리 가 서로 부 딪 힌 후에 두 개 미 는 동시에 고 개 를 돌려 계속 기어 간다. 입력 순서에 따라 개미 한 마리 의 T 초 후의 위 치 를 제시 한 후에 방향 을 향 해 달라 고 한다.
 
문제 풀이 방향:
  1. 개미 한 마리 가 서로 부 딪 힌 후 동시에 고 개 를 돌 리 는 것 은 맞 춤 형 으로 볼 수 있 는데 관건 적 인 문 제 는 바로 위치 변 화 를 구 하 는 것 이다.
  2. 위치 에 따라 작은 것 부터 큰 것 까지 정렬 하면 정렬 후 (befor 배열 과 after 배열) 모든 개미 가 상대 적 으로 위치 가 변 하지 않 고 방향 만 바 뀌 었 다 는 것 을 놀 라 게 발견 할 수 있 습 니 다.
 

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 using namespace std;

 6 

 7 const int maxn=10005;

 8 

 9 struct node

10 {

11     int   id, p, d;   //d    ，-1   ，0     ，1   。

12     bool operator < (const node& S)const

13     {

14         return p<S.p;

15     }

16 } befor[maxn],after[maxn];

17 

18 char dirname[][10]={"L","Turning","R"};

19 int  order[maxn];

20 

21 int main()

22 {

23     int  T, n, L, t, tcase=0;

24     int  ss[10005];

25     cin >> T;

26     while(T--)

27     {

28         scanf("%d%d%d",&L, &t, &n);

29         printf("Case #%d:
",++tcase);

30         for(int i=0; i<n; i++)

31         {

32             int  p, d;

33             char c;

34             scanf("%d %c",&p,&c);

35             d=(c=='L'?-1:1);

36             befor[i]=(node){i,p,d};

37             after[i]=(node){0,p+t*d,d};  //                

38         }

39         sort(befor,befor+n);

40         for(int i=0; i<n; i++)  //         ，                     

41             order[befor[i].id]=i;

42         sort(after,after+n);

43         for(int i=0; i<n-1; i++)

44             if(after[i].p==after[i+1].p)  after[i].d=after[i+1].d=0;

45         for(int i=0; i<n; i++)

46         {

47             int a=order[i];

48             if(after[a].p>=0&&after[a].p<=L)

49             {

50                 printf("%d %s
",after[a].p,dirname[after[a].d+1]);

51             }

52             else

53                 printf("Fell off
");

54         }

55         puts("");

56     }

57     return 0;

58 }