kevinkitty's blog

By kevinkitty, 11 years ago, In English

http://mirror.codeforces.com/contest/363/problem/D b1, b2, ..., bn (1 ≤ bi ≤ 104), p1, p2, ..., pm (1 ≤ pj ≤ 109), strategy one:if r bikes rented, correspondingly, then r person with max b,say set B; r bikes with min p, say set P. two:max b in B corresponds to max p in P,second-max b in B corresponds to second-max p in P, and so on.

so, if there are r bikes rented, we can use this strategy to calculate the min cost of share money, since some people may have b<p. for one r, we need O(r) time, that is O(n)

then: first, we need to know how many people could get bikes, since if we know r(number of bikes rented), we know the min cost of share money. So we can use binary search to find the max r, with O(nlogn) time.

second, if we fixed the max r, then we just need the strategy above to calculate the cost of all bikes, and the min cost of share money. then we could give the rest share money back to these boys. O(n) time.

total: O(nlogn)

  • Vote: I like it
  • -11
  • Vote: I do not like it