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

Автор gautam94, 11 лет назад, По-английски

386B - Fly, freebies, fly! Please help me understand this solution. 5711342 Is this the two pointers method. Why is the final answer ans = max(ans,j-i) ?

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

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

Here ans will contain the maximum of previous result and new result. j-i is the new result freebie can visit in T seconds starting from ith second.

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

This solution is similar to be brute force. So the main idea of problem is to find maximum in sorted timings of j-i, where a[i] + t <= a[j] (i <= j).

for example, first lucky student was i-th. it means that some next students whose time is not greater than a[i] + t are lucky too. We can find this maximum by brute force in submission 5711342 and by two pointers method. e.g. 5705879. Difference is that we don't change j, because if we know that a[i] + t <= a[j], this means that a[i + 1] + t <= a[j] too.