알고리즘 문제

이 문제에 대해 O (n) 알고리즘을 찾고 있지만 3 - 4 시간을 소비 한 후에도 알고리즘을 찾으려고합니다. 무차별 대항법은 시간이 만료 된 (O (n^2))입니다. 나는 그것을하는 방법에 관해서 혼란 스럽다. 솔루션에 동적 프로그래밍 솔루션이 필요합니까? 짧은 문제에알고리즘 문제

http://acm.timus.ru/problem.aspx?space=1&num=1794

은이 : 일부 원에 앉아 학생들과 그들의 각 하나는 그가 교사에서 질문을 할 수하고자 할 때를 스스로 선택의 여지가 있습니다

. 교사는 시계 방향으로 만 질문을 할 것입니다. 예를 들어 :

5 

3 3 1 5 5

이 5 명 학생이 있다는 것을 의미

1st student wants to go third 
2nd student wants to go third 
3rd student wants to go first 
4th student wants to go fifth 
5th student wants to go fifth.

질문에 같습니다 교사는 그들이 원하는 학생들의 최대 수는 차례를 얻을 수 있도록 질문을 시작해야하는 위치 . 당신은, 첫째로 다섯 번째 학생에서 2 명 학생들 시작하여 그것을 볼 수있다 (3, 5) 그들이 원하는대로 선택을 받고 5

3 3 1 5 5 

2 3 4 5 1

때문에이 특정 예를 들어, 대답은. 이 예를 들어 대답은 12 학생입니다 :

12 

5 1 2 3 6 3 8 4 10 3 12 7

때문에

5 1 2 3 6 3 8 4 10 3 12 7 

2 3 4 5 6 7 8 9 10 11 12 1

4 명의 학생이 자신의 선택이 성취 얻을.

출처

2011-01-09 Ravi

질문을 포함 시키거나 질문 텍스트에 더 잘 요약하십시오. – marcog

각 학생은 * 정확하게 * 가능한 시작 위치에 대한 소원을 얻습니다. "닫기"는 가치가 없습니다. 그래서 각 학생의 요구 된 말하기 위치는 그들이 먼저 말하고 싶은 사람을위한 투표로 재 해석 될 수 있습니다. 가장 많은 표를 얻은 선발 투수를 찾으라는 메시지가 나타납니다. 훨씬 어려운 문제는 학생들이 처음부터 어떻게 서클에 배치했는지를 묻는 것입니다.하지만이 문제가 시작될 때까지는 고정되어 있습니다 :-) –

@Steve : 좋은 해결책! –

실제로 다소 간단한 문제입니다. 학생 k가 j 번째가되기를 원한다면, (k - j + 1) 번째 (모듈로 n)가 처음 제시 될 때 만족할 것입니다. 이것은 간단한 O (n) 알고리즘으로 연결됩니다.

출처

2011-01-09 22:40:56

하지만 다른 학생들의 경쟁 욕구는 무엇입니까? 나는 이것을 너무 단순화했다고 생각합니다. –

@San Jacinto 아니, 나는하지 않았다. 간단한 O (n) 알고리즘을 알려 드리겠습니다. 일단 (i = 1 : n) sat [i - want [i] + 1] ++에 대해 각 시작 위치에 대해 얼마나 많은 학생들이 만족 하는지를 누적 한 목록을 반복하고, sat 값의 최대 값 인덱스를 찾으십시오. –

@San, Chris가 실제로 맞습니다. – marcog

알고리즘 문제

답변

관련 문제