天天看點

二分 + 模拟 - Carries Carries Problem's Link

Mean: 

給你n個數,讓你計算這n個數兩兩組合相加的和進位的次數.

analyse:

腦洞題.

首先要知道:對于兩個數的第k位相加會進位的條件是:a%(10^k)+b%(10^k)>=10^k.

想到這一點後就簡單了,枚舉每一位(最長9位),然後每個數都模10^k,然後排序二分.

排序後,如果b[i]+b[j]>=k,那麼i~j-1這段也滿足b[i]+b[j]>=k.

Time complexity: O(n*logn)

<a href="https://github.com/crazyacking/ACM-ICPC/blob/master/BNU/%E5%BC%B1%E6%A0%A1%E8%81%94%E8%90%8C%E5%8D%81%E4%B8%80%E5%A4%A7%E5%86%B3%E6%88%98%E4%B9%8B%E5%BC%BA%E5%8A%9B%E7%83%AD%E8%BA%AB%20-%20B/main.cpp" target="_blank">view code</a>