西安网站建设APP开发,做官网的步骤,新浪网站开发语言,软文推广软文营销来源#xff1a;牛客网#xff1a; 文章目录重新排列题解#xff1a;代码#xff1a;重新排列 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 牛牛有个很喜欢的字符串”…来源牛客网 文章目录重新排列题解代码重新排列 时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld 题目描述 牛牛有个很喜欢的字符串”puleyaknoi“。 牛牛有T个很长很长的字符串他很喜欢把字符串中的子串连续的某段打乱并且按照自己的喜好重新排列。 如果牛牛能把一段重新排列出他喜欢的字符串他就会把这个子串称作喜欢的子串。 牛牛是个懒人他不喜欢对太长的子串进行重排那样他会觉着眼镜很累。 你能帮他求出对于每个字符串最短的喜欢的子串的长度是多少吗 如果没有请输出-1。 输入描述: 第一行一个表示数据组数 接下来行每行一个字符串保证字符串只含小写字母 输出描述: 共T行每行一个答案 示例1 输入 复制
2
sxpuleyaaknoip
konijiwa输出 复制
11
-1说明 sxpuleyaaknoip中puleyaaknoi可以重排成puleyaknoia其中包含有puleyaknoi。 konijiwa不能重新排列出puleyaknoi所以是-1 备注: T≤10,字符串长度不超过10^5
题解
题意很明确我们来分析一下我们所要找的满足条件的区间没有办法一下确定也就是这个区间是需要不断调整的因为找到一个区间满足条件后有可能不是最简情况还能再缩所以我们可以采用尺取法 我们一开始确定左边界L0然后不断更新右边界r直到r满足条件这样就确定了一个区间记录答案然后左边界L右移一位然后右边界在原先的基础上找满足情况的区间更新区间最小值这样一直循环我们找到了所有满足情况的区间并取得最小值所以找到最优解 记得L右移动一位时将原本L位置的数据删除因为原L的数已经不在现区间里了 详细看代码
代码
#includebits/stdc.h
using namespace std;
string wpuleyaknoi;
const int maxn1e59;
int a[maxn]{0};
int b[maxn]{0};
const int INF1e69;
bool check()
{for(int i0;i26;i){if(b[i]a[i]b[i])return 0;}return 1;
}
int main()
{int n;cinn;for(int i0;iw.length();i){b[w[i]-a];}while(n--){string s;cins;int l,r,totINF;for(l0,r0;ls.length();l){while(check()0rs.length()){a[s[r]-a];r;}if(check()){totmin(tot,r-l);}a[s[l]-a]--;}if(totINF)cout-1endl;else couttotendl;}
}
