天天看点

二分 + 模拟 - 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>