Handshakes

7418 단어 sha
제목 링크: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=150371
제목:
    n 을 입력 하면 n 명 이 방 에 들 어 갈 것 이 고 들 어 오 는 사람마다 방 안의 모든 사람과 악 수 를 해 야 한 다 는 뜻 이다.어느 때 든 세 명의 학생 이 한 팀 경기 에 참가 할 수 있 는데 이것 은 하루 가 끝 날 때 까지 계속 된다.들 어 온 사람 은 더 이상 시합 하 는 사람과 악 수 를 할 필요 가 없다.각 사람 에 게 1 ~ n 번 호 를 주 고 입력 한 두 번 째 줄 은 각 번호 의 악수 횟수 를 표시 할 수 있 습 니 다. 이 횟수 일 수 있 는 지, 가능 하 다 면 Possible 을 출력 하고 가능 한 방 에 들 어 가 는 순 서 를 출력 합 니 다.불가능 하면 Impossible 을 출력 합 니 다.
    주의: 한 번 에 몇 조 의 세 명의 학우 가 단체 경기 에 참가 할 수 있 습 니 다.
   사례:
   1)input
       5
       2 1 3 0 1
       output
       Possible
       4 5 1 3 2
   2)input
        4
         0 2 1 1 
         output
         Impossible
사고 분석:
         0, 1, 2, 3.
         방 에 x 명 이 있 으 면 악 수 를 x 번 해 야 한다. 이것 은 먼저 악 수 를 x 번 하 는 사람 이 비어 있 는 지, 비어 있 지 않 으 면 그 중 한 명 을 찾 아 새로운 배열 에 저장 해 야 한다. 그렇지 않 으 면 방 에 있 는 사람 을 경기 에 보 내야 한다. 매번 에 3 명 씩 가서 악수 x - 3 번 하 는 사람 이 비어 있 는 지, 비어 있 는 지 찾 으 면 3 명 을 더 찾 아야 한다.빈 상태 에서 순환 을 벗 어 나 지 않 을 때 까지 (남 은 인원 은 x - 경기 인원 + 1), 또는 정상적으로 순환 을 벗 어 나 큰 순환 을 벗 어 날 때 까지.
       메모: 출력 할 때 끝 에 빈 칸 이 없습니다.
원본 코드 는 다음 과 같 습 니 다:
 
 1 #include<iostream>

 2 #include<vector>

 3 #define maxn 200000

 4 using namespace std;

 5 vector<int>a[maxn];

 6 int b[maxn];

 7 int main()

 8 {

 9     int n,i,s=0,x=0,m;

10     cin>>n;

11     for(i=0;i<n;i++)

12     {

13         cin>>m;

14         a[m].push_back(i+1);

15     }

16     while(s<n)               //      

17     {

18         if(!a[x].empty())               //           

19         { 

20             b[s++]=a[x][a[x].size()-1];

21             a[x].pop_back();

22             x++;

23         }

24         else

25         {

26             for(i=3;i<=x;i=i+3)

27                 if(!a[x-i].empty())

28                 {

29                     b[s++]=a[x-i][a[x-i].size()-1];

30                     a[x-i].pop_back();    

31                     break;

32                 }

33             if(i>x)break;

34             x=x-i+1;

35         }

36     }

37     if(s>=n)

38     {

39         cout<<"Possible"<<endl<<b[0];   

40         for(i=1;i<n;i++)

41             cout<<" "<<b[i];

42         cout<<endl;

43     }

44     else

45         cout<<"Impossible"<<endl;

46     return 0;

47 }

 
 
 

좋은 웹페이지 즐겨찾기