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)
Carries
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)