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

Автор zarif_2002, история, 6 лет назад, По-английски

I have solved this problem with binary search before. https://codeforces.net/contest/1156/problem/C But, I am trying to find out a deque solution but it fails at test 7.Why? 54565879 the algo is here. 1. sort the vector, 2. push every element at the end of the dq, 3. while pushing we would check if the difference between back and front element is greater than z(q.back() — q.front() >= z). if this condition is true, then increment the ans and pop the front and back elements. 4. when we finished traversing through the array, we get the answer.

what's wrong? please.

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

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

I think your approach is wrong. I had a similar approach and I also got WA on test 7. Take a look at my comment which I wrote after that contest (it contains a test on which most of the greedy solutions fail (your solution fails on it, too)).