PAT A1049 Counting Ones (30 分)

The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (≤2^ ​30​ ).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input:

12

Sample Output:

5

以下是AC的代码：

#include<cstdio>
int main(void){
	int n,a=1,ans=0;
	int left,now,right;
	scanf("%d",&n);
	while(n/a != 0){
		left=n/(a*10);
		now = n/a%10;
		right=n%a;
		if(now==0) ans+=left*a;
		else if(now == 1) ans+=left*a+right+1;
		else ans+=(left+1)*a;
		a*=10;
	}
	printf("%d",ans);
	return 0;
}
           

思路：

这道题难就难在找数 1 出现次数的规律。

比如数字 30710，1，2，3，4，5位分别对应，0，1，7，0，3，我们可以分别数出来每一位上能出现1的个数，加起来就是总的1的个数。

第一位 0，这是小于1 的，在0的左边为 0000 到 3070 的时候，0位才可能取到1，总的有3071次；

第二位 1，等于1，只有左边取000 到 306，右边取0-9，一共3070次，或者左边取307，右边只能取0，+1次；

第三位，7大于1，只有左边取00-30，右边取00-99，可以取到1，一共3100次；

第四位，0小于1，只有左边取0-2，右边取000-999，才可能取到1，一共3000次；

第五位，3大于1，右边可以是0000-9999，一共10000个；

所以总的1有 ans = 3071+3071+3100+3000+10000个。

用类似的思路处理题目给的数字就可以了。