stl set写这题过得去吗

Qerucy @ 2023-10-18 16:31:14

by Qerucy @ 2023-10-18 16:31:37

代码：

#include<bits/stdc++.h>

using namespace std;

multiset<int>s; 

int n,k;
int a[3000010];

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=0;i<k;i++){
        s.insert(a[i]);
    }

    for(int i=1;i<=n-k+1;i++){
        s.insert(a[i+k-1]);
        auto it=s.find(a[i-1]);
        s.erase(it);
        printf("%d ",*s.begin());
    }

    while(!s.empty()){
        s.erase(s.begin());
    }

    for(int i=0;i<k;i++){
        s.insert(-a[i]);
    }

    puts("");

    for(int i=1;i<=n-k+1;i++){
        s.insert(-a[i+k-1]);
        auto it=s.find(-a[i-1]);
        s.erase(it);
        printf("%d ",-*s.begin());
    }
    return 0;
} 

by ___A__ @ 2023-10-18 16:32:36

https://www.luogu.com.cn/record/103521091

by Qerucy @ 2023-10-18 16:36:02

@_A 求代码qwq，我开完隐了（

by ___A__ @ 2023-10-18 16:55:38

@iyag

#include<bits/stdc++.h>
using namespace std;
multiset<int>st;
const int N=1e6+50;
int a[N],n,m,tmp=1,ans[N][2];
multiset<int>::iterator it;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void print(int x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>9){
        print(x/10);
    }
    putchar(x%10+'0');
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(i<=m){
            st.insert(a[i]);
        }
    }
    it=st.begin();
    ans[0][0]=*it;//最小值
    it=st.end();
    it--;
    ans[0][1]=*it;//最大值
    for(int i=m+1;i<=n;i++){
        st.erase(st.find(a[tmp++]));
        st.insert(a[i]);
        it=st.begin();
        ans[i-m][0]=*it;
        it=st.end();
        it--;
        ans[i-m][1]=*it;
    }
    for(int j=0;j<2;j++){
        for(int i=0;i<=n-m;i++){
            print(ans[i][j]);
            putchar(' ');
        }
        putchar('\n');
    }
}