POJ 3320 Jessica's Reading Problem——尺取法

网友投稿 850 2022-11-28

POJ 3320 Jessica's Reading Problem——尺取法

POJ 3320 Jessica's Reading Problem——尺取法

题意：给定一组数，其中有一些重复数字，求一个长度最小的区间，要求这个区间内包含这组数的全部数字。

如1 8 8 8 1输出2

思路：尺取法求解，用map判断是否出现

#include #include #include using namespace std;const int maxn = 1e6 + 10;int n, s, a[maxn];map m;int main(){ while (scanf("%d", &n) == 1) { m.clear(); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (!m[a[i]]) { m[a[i]] = 1; s++; } } m.clear(); int L = 0, R = 0, sum = 0, ans = maxn; for (R = 0; R < n; R++) { if (!m[a[R]]) { sum++; } m[a[R]]++; if (sum == s) { while (sum == s) { ans = min(ans, R - L + 1); m[a[L]]--; if (!m[a[L]]) { sum--; } L++; } } } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数字 输出 判断
上一篇:POJ 2456 Aggressive cows——二分查找（最大化最小值）
下一篇:POJ 3276 Face The Right Way——开关问题
相关文章

 发表评论

暂时没有评论，来抢沙发吧~