題目來(lái)源：

藍(lán)橋杯 2023 省 A]更小的數(shù) - 洛谷

這題只需要用到雙指針就OK~

思路1：

• 翻轉(zhuǎn)數(shù)組的子數(shù)組，然后進(jìn)行比較大小
• 將翻轉(zhuǎn)后的數(shù)組存儲(chǔ)在字符串$k$中，然后將字符串$k$與字符串$a$進(jìn)行逐一元素比較（因?yàn)橹皇沁M(jìn)行了部分元素的翻轉(zhuǎn)，看成整數(shù)的話，位數(shù)是一一對(duì)應(yīng)的，且不需要考慮首項(xiàng)是$0$的情況），如果某一元素小的話，就返回$true,res+1$
• 這里還要說(shuō)一下本題暴力求解將字符串轉(zhuǎn)換為數(shù)值，哪怕是開(kāi)$longlong$ 也是裝不下的。因?yàn)榍?0%的數(shù)據(jù)都有$100$位！！

暴力：40’（過(guò)了前四個(gè)樣例）

#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$的想法，發(fā)現(xiàn)多比較了一些區(qū)間，這里進(jìn)行優(yōu)化。我們枚舉翻轉(zhuǎn)區(qū)間的左端點(diǎn)和右端點(diǎn)，然后判斷翻轉(zhuǎn)的這個(gè)區(qū)間中的幾個(gè)數(shù)字的大小就好了。
• 如何判斷？因?yàn)橐容^$num$和$nu{m}_{new}$，所以可以用兩個(gè)指針$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;
}