D - Permutation Subsequence(AtCoder Beginner Contest 352)

本文主要是介绍D - Permutation Subsequence(AtCoder Beginner Contest 352)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:

D - Permutation Subsequence (atcoder.jp)

题目大意：

分析：

相对于是记录一下每个数的位置 然后再长度为k的区间进行移动 然后看最大的pos和最小的pos的最小值是多少 有点类似于滑动窗口

用到了java里面的 TreeSet和Map TreeSet存的是数的位置 TreeSet里面有se.last() 获取当前这个里面的最后的这个元素 也就是最大最 se.first()也就是获取当前这个里面的第一个元素 也就是最小的 然后随着移动 当然要删除掉最左边的那个元素 也就是 se.remove((i + k - 1) 这个元素的位置)

代码：

import java.util.*;public class D2 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();var mp = new HashMap<Integer, Integer>();for(int i = 1; i <= n; i ++ ) {int x;x = sc.nextInt();mp.put(x, i); // 表示的是x的下标是i}var se = new TreeSet<Integer>();int ret = n;for(int i = 1; i < k; i ++ ) {se.add(mp.get(i));}for(int i = k; i <= n; i ++ ) {se.add(mp.get(i));int dis = se.last()-se.first();ret = Math.min(ret, dis);//去除当前这个容器的左边这个数 也就是向右移动一下se.remove(mp.get(i - k + 1));}System.out.print(ret);}
}

这篇关于D - Permutation Subsequence(AtCoder Beginner Contest 352)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---