本题与P3512有何区别,改了改代码,50pts
查看原帖
本题与P3512有何区别,改了改代码,50pts
758581
name1ess_0123210楼主2024/8/27 17:18
#include<bits/stdc++.h>

using namespace std;

const int mysize = 5e4 + 1;
int d[mysize];
int max_win[mysize] = {}, min_win[mysize] = {};

int calculate_max_length(int d[], int n, int k, int &l, int &r) {
    int max_front = 1, max_tail = 0;
    int min_front = 1, min_tail = 0;
    int ans = -1;
    
    for (int i = 1; i <= n; i++) {
        while (max_front <= max_tail && d[i] > d[max_win[max_tail]]) {
            max_tail--;
        }
        max_win[++max_tail] = i;
        
        while (min_front <= min_tail && d[i] < d[min_win[min_tail]]) {
            min_tail--;
        }
        min_win[++min_tail] = i;
        
        while (d[max_win[max_front]] - d[min_win[min_front]] > k) {
            if (max_win[max_front] > min_win[min_front]) {
                min_front++;
            } else {
                max_front++;
            }
        }
        
        if (ans < i - max(max_win[max_front - 1] + 1, min_win[min_front - 1] + 1) + 1) {
            ans = i - max(max_win[max_front - 1] + 1, min_win[min_front - 1] + 1) + 1;
            l = max(max_win[max_front - 1] + 1, min_win[min_front - 1] + 1);
            r = i;
        }
    }
    
    return ans;
}

int main() {
    int n, k;
    int ans1 = -1, ans2 = -1;
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
    }
    
    sort(d + 1, d + n + 1);
    
    int l1 = 0, r1 = 0;
    ans1 = calculate_max_length(d, n, k, l1, r1);
    
    for (int i = l1; i <= r1; i++) {
        d[i] = d[r1 + (i - l1 + 1)];
    }
    
    n -= (r1 - l1 + 1);
    
    fill(max_win, max_win + n + 1, 0);
    fill(min_win, min_win + n + 1, 0);
    
    int l2 = 0, r2 = 0;
    ans2 = calculate_max_length(d, n, k, l2, r2);
    
    cout << ans1 + ans2;
    
    return 0;
}

用滑动窗口做的,两个单调队列分别维护子区间的最大值最小值。排列完一个陈列架之后(找到了第一个最长子区间之后)在原数组中把已经被选择的钻石删去,然后再找一次最长子区间.两个长度相加就是答案

2024/8/27 17:18
加载中...