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)

view code