2023蓝桥杯省模拟赛附近最小

2023蓝桥杯省模拟赛附近最小

这个题算是一个经典的数据结构入门题了，写了几个解法水一篇文章

map维护

时间复杂度nlgn，但是常数比较大，所以只能过90%数据

#include 
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
int a[N];
void solve()
{
    int n, k;
    cin >> n;
    for (int i = 1; i 
        cin > a[i];
    }
    cin >> k;
    mapmp;
    int l = 1, r = min(k + 1, n);
    for (int i = 1; i 
        int l1 = max(1, i - k), r1 = min(n, k + i);
        if (l1  l)
            mp[a[l]]--;
        if (r1  r)
            mp[a[r1]]++;
        if (mp[a[l]] == 0)
            mp.erase(a[l]);
        l = l1, r = r1;
        cout 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //    cin  T;
    while (T--)
    {
        solve();
    }
    return 0;
}

单调队列

这算是题解区看到的最多的解法了，刚开始也没往这方面想，直接无脑贴了个线段树上去

代码里面有注释

时间复杂度是线性的，但是deque的常数是stl里面都算很大的，所以也比较慢，可以尝试用数组模拟deque

#include
#include
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int a[N];
int main()
{
    int n, k;
    cin >> n;
    deque dq;
    for (int i = 1; i > a[i];
    cin >> k;
    for (int i = n + 1; i 
        while (!dq.empty() && a[dq.back()]  a[i])
            dq.pop_back();
        dq.push_back(i);
        while (i - 2 * k  dq.front())
            dq.pop_front();
        if (i > k)  cout 
    return x & (-x);
}
int sum(int x) {
    int ans = 0;
    while (x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
void change(int x, int p) {
    while (p
        tree[p] += x;
        p += lowbit(p);
    }
}
void solve()
{
    int n,k;
    cin  n;
    for (int i = 1; i  a[i];
    int mi = 0x3f3f3f3f;
    cin >> k;
    int l = 1, r = min(k + 1, n),x=0x3f3f3f3f;
    for (int i = 1; i 
        int l1 = max(1, i - k), r1 = min(n, k + i);
        if (l1  l)
            change(-1, a[l]);
        if (r1  r)
            change(1, a[r1]);
        int x = 1, y = 1e6 + 1;
        while (x  1;
            if (sum(mid) >= 1)
                y = mid;
            else
                x = mid + 1;
        }
        l = l1, r = r1;
        cout 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //    cin  T;
    while (T--)
    {
        solve();
    }
    return 0;
}

    return x & (-x);
}
int sum(int x) {
    int ans = 0;
    while (x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
void change(int x, int p) {
    while (p
        tree[p] += x;
        p += lowbit(p);
    }
}
int serach(int x) {
    int l = 1, r = len + 1;
    while (l > n;
    for (int i = 1; i > a[i],b[i]=a[i];
    int mi = 0x3f3f3f3f;
    cin >> k;
    sort(b + 1, b + n + 1);
    for ( int j = 1; j 
        if (b[j] != b[j-1])
            b[++len] = b[j];
    }
    int l = 1, r = min(k + 1, n),x=0x3f3f3f3f;
    for (int i = 1; i 
        int l1 = max(1, i - k), r1 = min(n, k + i);
        if (l1  l) {
            change(-1, serach(a[l]));
        }
        if (r1  r)
            change(1, serach(a[r1]));
        int x = 1, y = len + 1;
        while (x = 1)
                y = mid;
            else
                x = mid + 1;
        }
        l = l1, r = r1;
        cout 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //    cin  T;
    while (T--)
    {
        solve();
    }
    return 0;
}

public:
int tree[110];
int lowbit(int x){
    return x&-x;
}
int sum(int x){
    int ans=0;
    while(x){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
void change(int pos,int x){
    while(pos
        tree[pos]+=x;
        pos+=lowbit(pos);
    }
}
    vector
        vector
            int mid=l+r1;
            if(sum(mid)=x)
            r=mid;
            else
            l=mid+1;
        }
        if(r-51
            change(a[i-1]+51,-1);
            change(a[i+k-1]+51,1);
            l=1,r=105;
        while(l
            int mid=l+r1;
            if(sum(mid)=x)
            r=mid;
            else
            l=mid+1;
        }
        if(r-51
    int n,k;
    cin  n;
    for (int i = 1; i > st[i][0];
    for (int i = 2; i > k;
    for (int i = 1; (1 
        for (int j = 1; j + (1 
        int l = max(1, i - k), r = min(n, k + i);
        int len = r - l + 1,mi=0x3f3f3f3f;
        //cout 
            mi = min(mi, st[l][lg2[len]]);
            l += (1 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //    cin  T;
    while (T--)
    {
        solve();
    }
    return 0;
}

    int l, r;
    int sum;
};
struct Segment_Tree
{
    tnode t[4 * N];
    void build(int root, int l, int r, int* A)
    {
        t[root].l = l, t[root].r = r;
        if (l == r)
            t[root].sum = A[l];
        else {
            int ch = root 
        if (l == t[root].l && r == t[root].r)
            return t[root].sum;
        int mid = t[root].l + t[root].r  1;
        if (r 
    int n,k;
    cin  n;
    for (int i = 1; i 
        int l = max(1, i - k), r = min(n, k + i);
        if (i