codeforces 1676F

2023-12-26 12:40:46

一道练习双指针的好题
题目链接

题目大意

给定 n n n个元素的数组 a a a,和正整数 k k k,需要你找到一组左右边界 l l l& r r r,使得 r ? l r-l r?l最大,并且使得每一个 x x x ( l < = x < = r ) (l<=x<=r) (l<=x<=r),在整个数组中至少出现 k k k

思路

读题不难看出,因为要满足每一个 x x x,所以我们需要找一组连续的子段
又发现我们需要找到满足出现次数的,所以我们可以先预处理一下数组,选出大于等于 k k k次的存到 v e c t o r vector vector里,因为数据是 1 e 9 1e9 1e9的,所以用不了桶了,我们用一个 m a p map map存,然后对 v e c t o r vector vector排序
关于双指针,有”形式“左边界和”输出“左边界和”输出“右边界,表示用于更新和输出的元素,如果相邻的元素相差大于 1 1 1就更新“形式”左边界是右边元素,用一个变量 m x mx mx存距离,如果当下元素减去“形式”左边界大于 m x mx mx了,说明又更大的,所以更新 m x mx mx,更新”输出“左边界和”输出“右边界

ACcode

#include<bits/stdc++.h>

using namespace std;

const int M = 2e5 + 9;
int a[M];

void solve() {
    int n, k;cin >> n >> k;
    for (int i = 0;i < M;i++)a[i] = 0;
    map<int, int>mp;

    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        mp[a[i]]++;
    }

    vector<int>c;
    for (auto x : mp)if (x.second >= k)c.push_back(x.first);
    if (!c.size()) {
        cout << -1 << '\n';
        return;
    }

    sort(c.begin(), c.end());
    int ri = c[0];int le = c[0];
    int l = c[0];
    int mx = 0;
    for (int i = 1;i < c.size();i++) {
        if (c[i] - 1 != c[i - 1]) {
            l = c[i];
            continue;
        }
        if (c[i] - l > mx) {
            mx = c[i] - l;
            le = l;
            ri = c[i];
        }
    }
    cout << le << ' ' << ri << '\n';
}

int main() {
    int t;cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

文章来源:https://blog.csdn.net/weixin_70831807/article/details/135215261
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。