算法问题

Question

我正在尝试为这个问题找到一个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

您可以看到，通过从第五名学生作为第一名开始，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

四个学生完成了他们的选择。

Answer 1

这实际上是一个相当简单的问题。如果学生k想成为要呈现的第j个，那么她将满足于第(k -j+1)个(模n)是第一个呈现的。这将引导您找到一个简单的O(n)算法。