PAT 解题报告 1049. Counting Ones (30)

1049. 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³⁰).

Output Specification:

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

Sample Input:

12

Sample Output:

5

题意

给定一个正整数 N(<=230)，要求计算所有小于 N 的正整数的各个位置上，1 出现的次数之和。

分析

比较有思维难度的一题，核心在于找规律。10ms 的时间限制表明了不能用常规的循环遍历来解决。需要从简单的 case 找规律，逐步扩大到常规的情况。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
//规律0~9有1个1；0~99有20个1；0~999有300个1...
using namespace std;
#define UP 10
int a[UP] = {0};
void mka(){
    for (int i=1; i<UP; i++) {
        double tmp = pow(10, i-1);
        a[i] = tmp * i;
    }
}
int getD(int n) {//得出几位数，123是3位数
    int cnt = 0;
    while (n!=0) {
        n/=10;
        cnt++;
    }
    return cnt;
}

int main()
{
    mka();
    int N;
    scanf("%d", &N);
    int sum = 0;
    while (N !=0 ) {//每次循环处理最高位
        if (N<10 && N>=1) {
            sum += 1;
            break;
        }
        int d = getD(N);//d位数
        double tmp = pow(10, d-1); int t = tmp;
        int x = N / t;//最高位的数字
        if (x ==1) {
            sum += N - x*t + 1;
        }
        else if (x>1) {
            sum += t;
        }
        sum += x*a[d-1];
        N -= x*t;//去掉最高位，处理后面的数
    }
    printf("%d", sum);

    return 0;
}