A way to solve 808E by ternary searching

Revision en1, by xzyxzy, 2017-05-17 17:18:37

I'm sorry to ask a foolish problem about my submission.So I share a way to solve 808E by ternary searching.

As we can see,W[i]=1,2,3.We sort the Souvenirs which have the same W[i] by their C[i].Then we know we will just choose a prefix for each W[i].

If we get X Souvenirs that W[i]=3,we remain (m-3X) to get Souvenirs that W[i]=1,2.Let's define F[i][x] the prefix sum of Souvenirs that W[i]=x.If we get Y Souvenirs that W[i]=2,our cost is F[X][3] + F[Y][2] + F[m-3X-2Y][1] (m-3X-2Y>=0).

We can try every X and use ternary searching to find the best Y.The complexity is O(nlogn).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English xzyxzy 2017-05-18 03:09:44 2 Tiny change: 'nirs that W[i]=1,2. Let's de' -> 'nirs that $W[i]=1,2$. Let's de'
en6 English xzyxzy 2017-05-17 17:22:51 4
en5 English xzyxzy 2017-05-17 17:22:00 2 Tiny change: 'nirs that W[i]=2,our cost ' -> 'nirs that $W[i]=2$,our cost '
en4 English xzyxzy 2017-05-17 17:21:29 93
en3 English xzyxzy 2017-05-17 17:19:24 8
en2 English xzyxzy 2017-05-17 17:19:00 6
en1 English xzyxzy 2017-05-17 17:18:37 634 Initial revision (published)