算法問題

我正在嘗試爲此問題找到一個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.

的問題是到哪裏應該老師開始提問，使學生的最大數目將獲得轉，因爲他們想要。對於這個特殊的例子，答案是5，因爲

3 3 1 5 5 

2 3 4 5 1

你可以看到，在開始第五學生爲1日，2名學生（3和5），因爲他們希望所得到的選擇。在這個例子中，答案是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

四個學生得到履行的選擇。

來源

2011-01-09 Ravi

請在問題文本中包含問題或更好的摘要。 – marcog 2011-01-09 22:29:31

每個學生都希望*完全*一個可能的起始位置，「關閉」是沒有價值的。所以每個學生要求的發言位置可以重新解釋爲對他們想先發言的人的投票。你被要求以最多的選票找到首發。更難的問題是詢問學生應該如何自己安排在圈子裏，但是到問題出現的時候，這是固定的:-) – 2011-01-09 22:37:04

這實際上是一個相當簡單的問題。如果學生k想成爲第j個呈現者，那麼如果第（k-j + 1）個（模n）是第一個出現的，她將會滿意。這應該會引導您使用簡單的O（n）算法。

來源

2011-01-09 22:40:56

回答

相關問題