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

网友投稿 912 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——开关问题
相关文章

 发表评论

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