题目描述

一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数。

例如 1135 是一个数位递增的数，而 1024 不是一个数位递增的数。

给定正整数 $n$n，请问在整数 1 至 $n$n 中有多少个数位递增的数？

输入描述

输入的第一行包含一个整数 $n(1<n<10^6)$n(1<n<106)。

输出描述

输出一行包含一个整数，表示答案。

输入输出样例

示例

输入

30

输出

26

#include<bits/stdc++.h>
using namespace std;
string prank(string a)
{
		string newa=a;
		sort(newa.begin(),newa.end());
		return newa;
}

int main()
{
	int n=0;
	cin>>n;
	int num =0; 
	for(int i =1;i<=n;i++)
	{
		string a=to_string(i);
		string newa=prank(a);
		if(newa==a)
		{
			num++;
		 } 
	} 
	cout<<num<<endl;
	return 0;
}

或者是

#include <iostream>
using namespace std;

// 辅助函数：判断一个整数x是否是数位递增数，返回true表示是，false表示不是
bool isDigitIncreasing(int x)
{
    // 记录前一位（右边的数位），初始化为最后一位数字
    int prev = x % 10;
    // 去掉最后一位数字，继续处理前面的数位
    x = x / 10;
    
    // 当x还有数位时，循环比较
    while (x > 0)
    {
        // 提取当前位（左边的数位）
        int curr = x % 10;
        // 如果当前位 > 前一位（右边数位），不满足递增条件，返回false
        if (curr > prev)
        {
            return false;
        }
        // 更新前一位为当前位，继续处理更左边的数位
        prev = curr;
        x = x / 10;
    }
    // 所有数位都满足条件，返回true
    return true;
}

int main()
{
    int n;
    cin >> n;
    int count = 0; // 统计数位递增数的个数
    
    // 遍历1到n的所有整数
    for (int x = 1; x <= n; x++)
    {
        // 如果x是数位递增数，统计数+1
        if (isDigitIncreasing(x))
        {
            count++;
        }
    }
    
    cout << count << endl;
    return 0;
}