编程之美 1的数目

我一上来就是遍历着计算，但在面试或者应用中决计是不可行的。。。。

我们换一种思路，一个数abcdefg，我们计算出各位，十位，百位。。。有多少个1，加一起即可。。。

就23012来说，看百位上它为0，从1---23012中，百位上有多少个1取决于比它高的所有位决定。。。

100--199，1100--1199,2100--2199.。。。11100--11199,21100--21199,22100--22199.。。。共23*100个。。注意只看百位是否是1，不管其它位，因为其它位也按此方法计算，就不多不少了

就23112来说，看百位上它为1，从1---23112中，百位上有多少个1取决于比它高的所有位决定和所有的低位。。

100--199，1100--1199,2100--2199.。。。11100--11199,21100--21199,22100--22199.。。。共23*100个

100-112 共12+1个。。。所以23*100+12+1...

就其它百位大于100--199，1100--1199,2100--2199.。。。11100--11199,21100--21199,22100--22199.23100--23199共23*100个。。。

#include <iostream>#include <cstdio>using namespace std;long long N,iLowerNum,iCurrNum,iHigherNum,ans,iFactor;void solve(){ iLowerNum = 0; iCurrNum = 0; iHigherNum = 0; iFactor = 1; while(N / iFactor != 0) { //iLowerNum = N - (N / iFactor)* iFactor; iLowerNum = N - N % iFactor; iCurrNum = (N / iFactor) % 10; iHigherNum = N / (iFactor * 10); switch (iCurrNum) { case 0: ans += iHigherNum * iFactor; break; case 1: ans += iHigherNum * iFactor + iLowerNum + 1; break; default : ans += (iHigherNum + 1) * iFactor; break; } iFactor *= 10; }}int main(){ while(cin >> N) { ans = 0; solve(); cout << ans <<endl; } return 0;}