【蓝桥杯每日一题】4.11 更小的数（不用区间DP）

题目来源：

蓝桥杯 2023 省 A]更小的数 - 洛谷

这题只需要用到双指针就OK~

思路1：

• 翻转数组的子数组，然后进行比较大小
• 将翻转后的数组存储在字符串$k$中，然后将字符串$k$与字符串$a$进行逐一元素比较（因为只是进行了部分元素的翻转，看成整数的话，位数是一一对应的，且不需要考虑首项是$0$的情况），如果某一元素小的话，就返回$true,res+1$
• 这里还要说一下本题暴力求解将字符串转换为数值，哪怕是开$longlong$ 也是装不下的。因为前20%的数据都有$100$位！！

暴力：40’（过了前四个样例）

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=5010;string a;string fan(string b,int start,int end)
{for(int i=start,j=end;i<=j;i++,j--){char t=b[i];b[i]=b[j];b[j]=t;}return b;
}bool check(string a,string b)
{int len=a.size();for(int i=0;i<len;i++){if(a[i]<b[i]) return true;else if(a[i]>b[i]) return false;}return false;
}signed main()
{ll res=0;cin>>a;int l=a.size();string m=a;for(int i=0;i<l;i++){for(int j=i+1;j<l;j++){string k=fan(m,i,j);if(check(k,a)) {//cout<<"i="<<i<<" j="<<j<<endl;res++;			}	}}cout<<res;return 0;
}

思路2：双指针

• 顺着思路$1$的想法，发现多比较了一些区间，这里进行优化。我们枚举翻转区间的左端点和右端点，然后判断翻转的这个区间中的几个数字的大小就好了。
• 如何判断？因为要比较$num$和$nu{m}_{new}$，所以可以用两个指针$i,j$。若字符$a_i>a_j$，表明$nu{m}_{new}<num$，若字符$a_i<a_j$，表明$nu{m}_{new}>num$，否则$a_i==a_j$，令$i+1，j-1$，直到$i>j$。

AC代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=5010;string a;bool check(int l,int r)
{for(int i=l,j=r;i<=j;i++,j--){if(a[i]>a[j]) return true;else if(a[i]<a[j]) return false;}return false;
}signed main()
{ll res=0;cin>>a;int l=a.size();for(int i=0;i<l;i++){for(int j=i+1;j<l;j++){if(check(i,j)) res++;}}cout<<res;return 0;
}