题面描述

在云计算环境下，用户的访问行为多样且复杂。项目组决定根据用户在一定时间周期内的最低信任分来控制用户的授权等级。具体来说，需要设计一个程序，通过分析用户的历史信任分序列，输出每个时间周期内的最小信任分序列。

给定一个长度为 $N$ 的用户历史信任分序列和一个时间周期大小 $W$，程序需要输出长度为 $N-W+1$ 的最小信任分序列。对于每一个窗口 $[x_i, x_{i+1}, \dots, x_{i+W-1}]$，最小信任分 $m_i = \min\{x_i, x_{i+1}, \dots, x_{i+W-1}\}$。

思路

滑动窗口板子题，不会的可以先学一下。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, W;
    cin >> N >> W;
    vector<long long> x(N);
    for(auto &num : x) cin >> num;

    deque<int> dq; // 双端队列，存储索引
    vector<long long> res;

    for(int i=0; i<N; ++i){
        // 移除队列尾部所有大于当前元素的索引
        while(!dq.empty() && x[i] <= x[dq.back()]){
            dq.pop_back();
        }
        dq.push_back(i);
        // 移除队列头部不在窗口内的索引
        if(!dq.empty() && dq.front() <= i - W){
            dq.pop_front();
        }
        // 当窗口大小达到W时，记录当前最小值
        if(i >= W -1){
            res.push_back(x[dq.front()]);
        }
    }

    // 输出结果
    for(int i=0; i<res.size(); ++i){
        if(i != 0) cout << ' ';
        cout << res[i];
    }
    return 0;
}

python

import sys
from collections import deque

def main():
    import sys
    import sys
    N, W = map(int, sys.stdin.readline().split())
    x = list(map(int, sys.stdin.readline().split()))
    dq = deque()
    res = []
    for i in range(N):
        # 移除队列尾部所有大于当前元素的索引
        while dq and x[i] <= x[dq[-1]]:
            dq.pop()
        dq.append(i)
        # 移除队列头部不在窗口内的索引
        if dq[0] <= i - W:
            dq.popleft()
        # 当窗口大小达到W时，记录当前最小值
        if i >= W -1:
            res.append(x[dq[0]])
    print(' '.join(map(str, res)))

if __name__ == "__main__":
    main()

java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        int N = Integer.parseInt(first[0]);
        int W = Integer.parseInt(first[1]);
        String[] second = br.readLine().split(" ");
        long[] x = new long[N];
        for(int i=0; i<N; i++) x[i] = Long.parseLong(second[i]);
        
        Deque<Integer> dq = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            // 移除队列尾部所有大于当前元素的索引
            while(!dq.isEmpty() && x[i] <= x[dq.getLast()]){
                dq.removeLast();
            }
            dq.addLast(i);
            // 移除队列头部不在窗口内的索引
            if(!dq.isEmpty() && dq.peekFirst() <= i - W){
                dq.removeFirst();
            }
            // 当窗口大小达到W时，记录当前最小值
            if(i >= W -1){
                sb.append(x[dq.peekFirst()]);
                sb.append(' ');
            }
        }
        // 输出结果，去除最后一个空格
        System.out.println(sb.toString().trim());
    }
}