算法问题

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

您可以看到，从第 1 名第 5 名学生开始，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) 算法。