Advertisement
RaFiN_

Buy Low Sell High: cf - 867E

Jun 25th, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.61 KB | None | 0 0
  1.  
  2. Buy Low Sell High: cf - 867E
  3. Let's maintain two multisets, "unused" and "already sold". After taking input "x", I tried to sell this pairing with a previous element(which I'm gonna buy). Took the minimum valued element among "unused" + "already sold" stuffs, let's call it "y".
  4.  
  5. If(y < x) {
  6. if(y came from unused set) buy y and sell x.
  7. else if(y came from "already sold" set) put y in unused set and sell x.
  8. }
  9. else put "x" in unused set
  10. The solution actually comes from the idea — If I see that there's an "already sold" stuff smaller than x, it'd be optimal to sell "x" and not use y, rather than use y and buy x.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement