frog has nn integers a1,a2,…,ana1,a2,…,an, and she wants to add them pairwise.
Unfortunately, frog is somehow afraid of carries (进位). She defines hardness h(x,y)h(x,y) for adding xx and yy the number of carries involved in the calculation. For example, h(1,9)=1,h(1,99)=2h(1,9)=1,h(1,99)=2.
Find the total hardness adding nn integers pairwise. In another word, find
∑1≤i < j ≤ n h (ai,aj) ∑ 1 ≤ i < j≤ nh(ai,aj) .
The input consists of multiple tests. For each test:
The first line contains 11 integer nn (2≤n≤1052≤n≤105). The second line contains nn integers a1,a2,…,ana1,a2,…,an. (0≤ai≤1090≤ai≤109).
For each test, write 11 integer which denotes the total hardness.
题意：
给你n个数，问其中任意两个数相加能够有多少次进位。
例子：1+99=100，个位进位一次，十位进位一次，就是两次； 50+50 十位进位一次，就是一次。
#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define LL long long using namespace std; LL a[100010]; LL temp[100010]; int main() { LL t; while(cin>>t) { for(int i=0;i<t;i++) { cin>>a[i]; } LL mod=1; LL ans=0; for(int i=0;i<9;i++) { mod*=10; for(int j=0;j<t;j++) { temp[j]=a[j]%mod; // cout<<temp[j]<<"---"<<a[j]<<endl; } sort(temp,temp+t); LL tt; for(int j=0;j<t;j++) { tt=t-(lower_bound(temp+1+j,temp+t,mod-temp[j])-temp); ans+=tt; // cout<<tt<<endl; } } cout<<ans<<endl; } return 0; }函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置
要记住：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！~ 返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置
