Блог пользователя mike_wasabi

How to solve this problem ?
Автор mike_wasabi, история, 5 лет назад, По-английски

Give integer ranges A1, A2, .., AN. Number Ai is called the K-random number of the sequence if in K terms Any sequence of a sequence has at least one term equal to Ai and K is the smallest integer that satisfies this condition. Example: Range 1,2,3,1,2,2. Number 1 is a 3-random number; number 2 is a 3-random number; number 3 is a 4-random number Conditions: N <= 100000 and | Ai | <= 1000.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Run a loop from 1 to N. For each number, remember the last index where you found that number untill now (untill current index). For example, let's say that we are currently at index i. We do the following:

maxi[Ai] = max(maxi[Ai], i — last_index[Ai];

last_index[Ai] = i;

In the end you just calculate this for each number:

maxi[number] = max(maxi[number], N — last_index[number]);

→ Ответить