object022's blog

By object022, 12 years ago, In English

UPD:Minor mistakes in grammar and expression fixed.

Disclaimer: This is not an official editorial.

If you have better or easy-to-understand solutions and thoughts, feel free to share your idea. Also welcome to point out mistakes so I can fix it.

160A - Twins

It's obvious that you should take the most valueable coins. so sort values in non-decreasing order, then take coins from the most valueable to the least, until you get strictly more than half of total value.

Time complexity depends on the sorting algorithm you use. O(n^2) is also acceptable, but if you use bogosort which runs in O(n!)...

160B - Unlucky Ticket

Deal with the situation that "first half is strictly less than second half" first. the other one can be solved accordingly.

You can use greedy here: sort digits in first and second half seperately. then if the i-th digit in first half is always less than i-th in second half for 1<=i<=n, answer is YES.

Time complexity is as same as problem A. Count sort may run faster in O(n+10), but it's not necessary

Full text and comments »

  • Vote: I like it
  • +51
  • Vote: I do not like it