蓝桥杯3503 更小的数

问题描述

小蓝有一个长度均为 n 且仅由数字字符 0∼9 组成的字符串，下标从 0 到 n−1，你可以将其视作是一个具有 n 位的十进制数字 num，小蓝可以从 num 中选出一段连续的子串并将子串进行反转，最多反转一次。

小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 num_new​ 满足条件 num_new<num，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是 0，这是合法的。

输入格式

输入一行包含一个长度为 n 的字符串表示 num（仅包含数字字符 0∼9），从左至右下标依次为 0∼n−1。

输出格式

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

样例输入

210102

样例输出

8

 

枚举所有子串，对每个子串 s[i..j]，用双指针 i 和 j 从两端向中间移动，跳过相同字符，比较第一个不同的字符对，若 s[i] > s[j]，则计数

#include<iostream>
#include<cstring>
using namespace std;const int N = 5e3+10;
string s;int ans;//判断子串 s[i..j] 的反转是否比原子串小
void check(int i, int j)
{//跳过相同字符while(s[i]==s[j] && i<j){i++;j--;}//如果所有字符都相同，则反转后子串与原串相同，直接返回 if(i>=j) return;//反转后的子串比原串小if(s[i]>s[j]) ans++;return;
}int main()
{cin>>s;int len = s.size();for(int i=0; i<len-1; ++i){for(int j=i+1; j<len; ++j)  //确保子串至少有两个字符{check(i, j);}}cout<<ans;return 0;
}