PAT 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^30^).

Output Specification:

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

Sample Input:

12
           

Sample Output:

5
           

解答：剛開始計算時，使用了暴力求解，結果有兩個逾時，逾時的代碼如下一。後來借鑒了其他部落格的求解思路。解題時，需要考查數值的每位數，分别對該數的值為0、1和>=2進行考察，進而計算得到結果。

逾時代碼:

#include<iostream>

using namespace std;


int main()
{
	long long positive;
	int count = 0;
	
	cin >> positive;
	for(int i = 1; i <= positive; ++i)
	{
		int val = i;
		while(val)
		{
			if(val % 10 == 1)
			{
				count++;
			}
			val /= 10;
		}
	}
	cout << count << endl;
	return 0;
} 
           

AC代碼如下:

#include<iostream>

using namespace std;

using ll = long long;

int main()
{
	int N;
	int a = 1, left, right, now;
	int count = 0;
	
	cin >> N;
	while(N / a)
	{
		left = N / (a*10);
		right = N % a;
		now = N / a % 10;
		if( now == 0 )
		{
			count += left * a;
		}
		else if( now == 1 )
		{
			count += (left * a + right + 1);
		} 
		else 
		{
			count += (left+1)*a;
		}
		a = a * 10;
	}
	cout << count << endl;
	return 0;
}