像这种问最小值的我们一般都会想到二分
很明显,题目确实有二分性,则我们直接二分出答案去判断是否可以唯一确定位置即可
#include<iostream>
#include<unordered_set>
using namespace std;
const int N=110;
char s[N];
int n;
bool check(int x)
{
unordered_set<string>mp;
for(int i=1;i<=n-x+1;i++)
{
string sum;
for(int j=i;j<=i+x-1;j++)
sum+=s[j];
if(!mp.count(sum))mp.insert(sum);
else return false;
}
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}
我也是二分一遍过,但后来回来一想,单调性是啥
二分需要的其实不是单调性而是二分性,一半可以一半不行就能用二分