PAT 1049. Counting Ones (30)

Posted on Edited on In

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 (<=230).

Output Specification:

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

Sample Input:

12

Sample Output:

5

对于一个n为的数字，每次只考虑其中的一位，对于这一位可以产生多少一个1进行讨论。 假设给定一个数字为21087 考虑数字7，对于7这个位置要产生1，只有(0000-2108) 1 ，产生2109个1 考虑数字8，对于7这个位置要产生8，只有(000-210) 1 (0-9)，有2110个1 考虑数字0，对于0这个位置要产生1，那么只有(00-20) 1 (00-99) ，所以一共有21 * 100 = 2100个1 考虑数字1，对于1这个位置，有(0-1) 1 (000-999)和21(000-087)，共有2 * 1000 + 88 = 2088个1 考虑数字2，对于2这个位置要产生1，有1 (0000-9999) 共有10000个1 对于数字3，则一共产生18407个1 更一般地： 假设now是一个n位数的第now位，对now位置上面的数字进行讨论，cur是now在n位数的数位，left表示now左边的数字，right表示右边的数字，可得： 如何now位置的数字是0，那么可以产生left * cur个1 如何now位置的数字是1，那么可以产生left * cur + right + 1个1 否则，可以产生(left + 1) * cur个1 根据上面的算法描述，可以得到代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>

int main() {
    int n = 0, cur = 1, left = 0, right = 0, now = 0, ans = 0;
    scanf("%d", &n);
    while (n / cur != 0) {
        left = n / (cur * 10);
        right = n % cur;
        now = n % (cur * 10) / cur;
        if (now == 0) {
            ans += left * cur;
        } else if (now == 1) {
            ans += left * cur + right + 1;
        } else {
            ans += (left + 1) * cur;
        }
        cur *= 10;
    }
    printf("%d\n", ans);
}