头像

果子




离线:1天前


最近来访(10)
用户头像
itdef
用户头像
我是sun
用户头像
chen_57
用户头像
瑜huang
用户头像
anji
用户头像
牙口少女
用户头像
苍穹一粟
用户头像
foxfuns
用户头像
林大帅

活动打卡代码 AcWing 2. 01背包问题

果子
2天前

1 朴素做法

#include <iostream>
#include <algorithm>

using namespace std;
const int N=1005;

int main()
{
    int n,V;
    int v[N],w[N];
    int dp[N][N];
    cin>>n>>V;
    for(int i=1;i<=N;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=V;i++)dp[0][i] = 0;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=V;j++)
    {
        dp[i][j] = dp[i-1][j];
        if(v[i] <= j)
        {
            dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    }

    cout<<dp[n][V];
    return 0;
}

2 二维转一维

#include <iostream>
#include <algorithm>

using namespace std;
const int N=1005;

int main()
{
    int n,V;
    int v[N],w[N];
    int dp[N];
    cin>>n>>V;
    for(int i=1;i<=N;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=V;i++)dp[i] = 0;

    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    {
        dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }

    cout<<dp[V];
    return 0;
}




果子
4天前
#include <iostream>
#include<string>

using namespace std;
#define MAXSIZE 50
int Index_BF(string s,string t,int pos)  //返回模式串t在主串s中第pos个字符开始第一次出现的位置。若不存在,则返回值为-1
{
    int i=pos,j=0;
    while(i <= s.length()-1 && j <= t.length()-1)
    {
        if(s[i] == t[j])i++,j++;
        else i=i-j+1,j=0;
    }
    if(j > t.length()-1)return i-t.length();
    return -1;
}
void GetNext(int next[],string t)
{
    int j=0,k=-1;
    next[0]=-1;
    while(j<t.size()-1)
    {
        if(k == -1 || t[j] == t[k])
        {
            j++;
            k++;
            //改进算法
            if(t[j] != t[k])
                next[j]=k;
            else
                next[j]=next[k];
        }else
            k=next[k];
    }
}
int Index_KMP(string s,string t)
{
    int next[MAXSIZE];
    int i=0,j=0;
    GetNext(next,t);
    //for(int i=0;i<t.size();i++)cout<<next[i]<<' ';
    //cout<<endl;
    while(i < (int)s.length() && j < (int)t.length())
    {
        if(j==-1 || s[i] == t[j]){
            i++;
            j++;
        }
        else
            j=next[j];
    }
    if(j >= (int)t.length()){
        return (i-t.length());
    }
    else
        return -1;
}
int main()
{
    string s,t;
    int pos;
    cin>>s>>t;
    //cout<<Index_BF(s,t,pos);
    cout<<Index_KMP(s,t);
    return 0;
}




果子
5天前

因为string的size类型是size_t,一般是32位或者64位无符号整数;而-1是int类型,在与unsigned int(也可能是unsigned long等等,看你具体编译器)进行比较时会被提升为相应的无符号类型,而-1的二进制补码是全1,把全1的二进制码当做无符号数解释的时候是无符号数的最大值,所以-1是最大的。




果子
6天前
#include <iostream>

using namespace std;

//--------队列的顺序存储结构-------
#define MAXQSIZE 100  //队列可能达到的最大长度
typedef int QElemType;//存储的数据类型
typedef struct queue
{
    QElemType *base;  //存储空间的基地址
    int front;
    int rear;
}SqQueue;

bool InitQueue(SqQueue &Q)//构造一个空队列
{
    Q.base = new QElemType[MAXQSIZE];    //为队列分配一个最大容量为MAXQSIZE的数组空间
    if(!Q.base) exit(1);                 //存储分配失败
    Q.front=Q.rear=0;                    //头指针和尾指针置为零,队列为空
    return true;
}

int QueueLength(SqQueue &Q)//返回Q的元素个数,即队列的长度
{
    return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

bool EnQueue(SqQueue &Q,QElemType e)//插入元素e,为Q的新的队尾元素
{
    if((Q.rear+1) % MAXQSIZE == Q.front)
        return false;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1) % MAXQSIZE; //队尾指针加1
    return true;
}

bool DeQueue(SqQueue &Q,QElemType &e)//删除Q的队头元素,用e返回其值
{
    if(Q.front == Q.rear) return false;
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return true;
}

QElemType GetHead(SqQueue &Q)//返回Q的队头元素,不修改队头指针
{
    if(Q.front != Q.rear)   //队列非空
        return Q.base[Q.front];
}

void PrintQueue(SqQueue &Q)//打印队列元素
{
    cout<<"队列:";
    if(Q.front == Q.rear){
        cout<<"空"<<endl;
        return;
    }
    cout<<" [队头]-> ";
    for(int i=Q.front;i != Q.rear;i=(i + 1) % MAXQSIZE)//遍历队列
    {
        cout<<Q.base[i]<<" \n"[((Q.rear-i+MAXQSIZE) % MAXQSIZE) == 1];
    }
}
int main()
{
    SqQueue Q;
    InitQueue(Q);
    cout<<"初始化队列成功!"<<endl;
    char c='!';
    while(c!='0')
    {
        cin>>c;
        if(c == 'L'){
            cout<<"队列的长度为:"<<QueueLength(Q)<<endl;
        }else if(c == 'E'){
            int e;
            cin>>e;
            if(EnQueue(Q,e))
                cout<<"插入元素成功!"<<endl;
            else
                cout<<"队列已满!"<<endl;
        }else if(c == 'D'){
            int e;
            if(DeQueue(Q,e))
                cout<<"元素 "<<e<<" 出队成功!"<<endl;
            else
                cout<<"队列为空!"<<endl;
        }else if(c == 'G'){
            int e;
            e=GetHead(Q);
            cout<<"对头元素值为:"<<e<<endl;
        }else if(c == 'P'){
            PrintQueue(Q);
        }
    }   
    return 0;
}



分享 错误代码

果子
10天前
#include<iostream>
using namespace std;
struct Nod{
    int x;  //系数
    int y;  //指数
    Nod* next;
};
int main()
{
    //-------------------------------------输入
    Nod fir1,fir2,temp;
    fir1.next=NULL;
    fir2.next=NULL;
    int n1,n2;
    cin>>n1;
    Nod* s=NULL;
    for(int i=0,x=0,y=0;i<n1;i++)
    {
        cin>>x>>y;
        temp.x=x;
        temp.y=y;
        temp.next=NULL;
        if(s==NULL)
            fir1.next=&temp;
        else
            s->next=&temp;
        s=&temp;
    }
    cin>>n2;
    s=NULL;
    for(int i=0,x,y;i<n2;i++)
    {
        cin>>x>>y;
        temp.x=x;
        temp.y=y;
        temp.next=NULL;
        if(s==NULL)
            fir2.next=&temp;
        else
            s->next=&temp;
        s=&temp;
    }
    //-------------------------------------
    /*Nod fir3;
    Nod* f3=NULL;
    fir3.next=NULL;
    for(Nod *i=fir1.next,*j=fir2.next;i!=NULL && j!=NULL;)
    {
        if(i->y > j->y)
        {
            if(f3==NULL)
            {
                fir3.next=i;
                f3=i;
            }
            else
            {
                f3->next=i;
                f3=f3->next;
            }
            i=i->next;
        }else if(i->y < j->y)
        {
            if(f3==NULL)
            {
                fir3.next=j;
                f3=j;
            }
            else
            {
                f3->next=j;
                f3=f3->next;
            }
            j=j->next;
        }else
        {
            Nod tempp;
            tempp.x=i->x+j->x;
            tempp.y=i->y;
            if(f3==NULL)
            {
                fir3.next=&tempp;
                f3=&temp;
            }
            else
            {
                f3->next=&tempp;
                f3=f3->next;
            }
            i=i->next;
            j=j->next;
        }
    }*/
    s=fir1.next;

        cout<<s->x<<' '<<s->y<<' '<<endl;

    //-----------------------------------------
    return 0;
}



果子
12天前
#include<iostream>
#include<deque>
#include<vector>
#include<string>
#include<algorithm>
#include<ctime>
using namespace std;

class Person
{
public:
    Person(string name,int score)
    {
        this->m_Name = name;
        this->m_Score = score;
    }

    string m_Name; //姓名
    int m_Score;// 平均分
};
void createPerson(vector<Person>&v)
{
    string nameSeed = "ABCDE";
    for(int i=0;i<5;i++)
    {
        string name = "选手";
        name += nameSeed[i];

        int score = 0;

        Person p(name,score);

        //将创建的Person对象 放入到容器中
        v.push_back(p);
    }
}
void setScore(vector<Person>&v)
{
    for(int i=0;i<v.size();i++)
    {
        //将评委的分数 放入到一个deque容器中
        deque<int> d;
        for(int i=0;i<10;i++)
        {
            int score=rand()%41+60;
            d.push_back(score);
        }

        //排序
        sort(d.begin(),d.end());

        //去除最高和最低分
        d.pop_back();
        d.pop_front();
        //取平均分
        int sum = 0;
        for(int i=0;i<d.size();i++)
            sum+=d[i];
        int avg=sum/d.size();
        v[i].m_Score=avg;
    }
}
int main()
{
    //随机数种子
    srand((unsigned int)time(NULL));
    //1.创建5名选手
    vector<Person> v;//存放选手的容器
    createPerson(v);
    //测试
    /*
    for(int i=0;i<v.size();i++)
        cout<<"姓名: "<<v[i].m_Name<<" 分数: "<<v[i].m_Score<<endl;
    */
    //2.给5名选手打分
    setScore(v);
    //3.显示最后得分
    for(int i=0;i<v.size();i++)
        cout<<"姓名: "<<v[i].m_Name<<" 分数: "<<v[i].m_Score<<endl;
    return 0;
}#include<iostream>
#include<deque>
#include<vector>
#include<string>
#include<algorithm>
#include<ctime>
using namespace std;

class Person
{
public:
    Person(string name,int score)
    {
        this->m_Name = name;
        this->m_Score = score;
    }

    string m_Name; //姓名
    int m_Score;// 平均分
};
void createPerson(vector<Person>&v)
{
    string nameSeed = "ABCDE";
    for(int i=0;i<5;i++)
    {
        string name = "选手";
        name += nameSeed[i];

        int score = 0;

        Person p(name,score);

        //将创建的Person对象 放入到容器中
        v.push_back(p);
    }
}
void setScore(vector<Person>&v)
{
    for(int i=0;i<v.size();i++)
    {
        //将评委的分数 放入到一个deque容器中
        deque<int> d;
        for(int i=0;i<10;i++)
        {
            int score=rand()%41+60;
            d.push_back(score);
        }

        //排序
        sort(d.begin(),d.end());

        //去除最高和最低分
        d.pop_back();
        d.pop_front();
        //取平均分
        int sum = 0;
        for(int i=0;i<d.size();i++)
            sum+=d[i];
        int avg=sum/d.size();
        v[i].m_Score=avg;
    }
}
int main()
{
    //随机数种子
    srand((unsigned int)time(NULL));
    //1.创建5名选手
    vector<Person> v;//存放选手的容器
    createPerson(v);
    //测试
    /*
    for(int i=0;i<v.size();i++)
        cout<<"姓名: "<<v[i].m_Name<<" 分数: "<<v[i].m_Score<<endl;
    */
    //2.给5名选手打分
    setScore(v);
    //3.显示最后得分
    for(int i=0;i<v.size();i++)
        cout<<"姓名: "<<v[i].m_Name<<" 分数: "<<v[i].m_Score<<endl;
    return 0;
}


分享 deque容器

果子
12天前
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;

void printDeque(const deque<int> &d)
{
    for(deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
    {
        cout<<*it<<' ';
    }
    cout<<endl;
}

void test01()//构造函数
{
    deque<int> d1;
    for(int i=0; i<10; i++)
        d1.push_back(i);
    printDeque(d1);

    deque<int>d2(d1.begin(),d1.end());
    printDeque(d2);

    deque<int>d3(10,100);
    printDeque(d3);

    deque<int>d4 = d3;
    printDeque(d4);
}

void test02()//赋值操作
{
    deque<int> d1;
    for (int i = 0; i < 10; i++)
    {
        d1.push_back(i);
    }
    printDeque(d1);

    deque<int>d2;
    d2 = d1;
    printDeque(d2);

    deque<int>d3;
    d3.assign(d1.begin(), d1.end());
    printDeque(d3);

    deque<int>d4;
    d4.assign(10, 100);
    printDeque(d4);
}
void test03()//大小操作  deque没有容量的概念
{
    deque<int> d1;
    for(int i=0; i<10; i++)
        d1.push_back(i);
    printDeque(d1);

    //判断容器是否为空
    if(d1.empty())
        cout<<"d1大小为空!"<<endl;
    else
    {
        cout<<"d1大小不为空"<<endl;
        //统计大小
        cout<<"d1的大小为"<<d1.size()<<endl;
    }

    //重新指定大小
    d1.resize(15,1);
    printDeque(d1);

    d1.resize(5);
    printDeque(d1);
}
void test04()//插入和删除 插入和删除提供的位置是迭代器!
{
    deque<int> d1;
    for(int i=0;i<10;i++)
        d1.push_back(i);//头插
    printDeque(d1);

    //头插
    d1.push_front(1);
    printDeque(d1);

    //头删 尾删
    d1.pop_front();
    d1.pop_back();
    printDeque(d1);

    //insert插入
    d1.insert(d1.begin(),1000);
    printDeque(d1);

    d1.insert(d1.begin(),2,10000);
    printDeque(d1);

    deque<int> d2;
    d2.push_back(888);
    d2.insert(d2.begin(),d1.begin(),d1.end());
    printDeque(d2);

    //删除
    deque<int>::iterator it=d1.begin();
    it++;
    d1.erase(it);
    printDeque(d1);

    //按区间方式删除
    d1.erase(d1.begin(),d1.end());
    printDeque(d1);
}
void test05()//数据存取
{
    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_back(30);
    d.push_front(100);
    d.push_front(200);
    d.push_front(300);
    //通过[]的方式访问元素
    for(int i=0;i<d.size();i++)
        cout<<d[i]<<' ';
    cout<<endl;
    //通过at的方式访问元素
    for(int i=0;i<d.size();i++)
        cout<<d.at(i)<<' ';
    cout<<endl;

    cout<<"第一个元素为: "<<d.front()<<endl;
    cout<<"最后一个元素为: "<<d.back()<<endl;
}
void test06()//排序
{
    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_back(30);
    d.push_front(100);
    d.push_front(200);
    d.push_front(300);
    //300 200 100 10 20 30
    printDeque(d);

    //排序  默认排序规则 从小到大 升序
    //对于支持随机访问的迭代器的容器,都可以利用sort算法直接对其进行排序
    //vector容器也可以利用 sort进行排序
    sort(d.begin(),d.end());
    cout<<"排序后的结果:"<<endl;
    printDeque(d);

}
int main()
{
    //test01();//构造函数
    //test02();//赋值操作
    //test03();//大小操作
    //test04();//插入和删除
    //test05();//数据存取
    test06();//排序
    return 0;
}



果子
20天前
#include<iostream>
#include<vector>
using namespace std;
void printVector(vector<int> & v)
{
    for(int i=0; i < v.size();i++)
        cout<<v[i]<<' ';
    cout<<endl;
}
void test01()//vector容器构造
{
    vector<int> v1;//默认构造 无参构造

    for(int i = 0; i < 10; i++)
        v1.push_back(i);

    printVector(v1);

    //通过区间方式进行构造
    vector<int> v2(v1.begin(),v1.end());
    printVector(v2);

    //n个elem方式构造
    vector<int> v3(10,100);
    printVector(v3);

    //拷贝构造
    vector<int> v4(v3);
    printVector(v4);
}
void test02()//赋值
{
    vector<int> v1;
    for(int i=0;i<10;i++)
        v1.push_back(i);
    printVector(v1);

    //赋值 operator=
    vector<int> v2;
    v2=v1;
    printVector(v2);

    //assign
    vector<int> v3;
    v3.assign(v1.begin(),v1.end());
    printVector(v3);

    //n个elem 方式赋值
    vector<int> v4;
    v4.assign(10,100);
    printVector(v4);
}
void test03()//容量和大小
{
    vector<int> v1;
    for(int i=0;i<10;i++)
        v1.push_back(i);
    printVector(v1);

    if(v1.empty())
        cout<<"v1为空"<<endl;
    else 
    {
        cout<<"v1不为空"<<endl;
        cout<<"v1的容量为"<<v1.capacity()<<endl;
        cout<<"v1的大小为"<<v1.size()<<endl;
    }

    //重新指定大小
    v1.resize(15,100);
    printVector(v1);

    v1.resize(5);
    printVector(v1);
}
void test04()//插入和删除
{
    vector<int> v1;
    for(int i=0;i<10;i++)
        v1.push_back(i);//尾插
    printVector(v1);

    //尾删
    v1.pop_back();
    printVector(v1);

    //插入
    v1.insert(v1.begin(),100);
    printVector(v1);

    v1.insert(v1.begin(),2,200);
    printVector(v1);

    //删除
    v1.erase(v1.begin());
    printVector(v1);

    v1.erase(v1.begin(),v1.begin()+2);
    printVector(v1);

    //清空
    v1.clear();
    printVector(v1);
}
void test05()//数据存取
{
    vector<int> v1;
    for(int i=0;i<10;i++)
        v1.push_back(i);//尾插

    //利用[]方式访问数组中元素
    for(int i = 0;i < v1.size(); i++)
        cout<<v1[i]<<' ';
    cout<<endl;

    //利用at方式访问元素
    for(int i = 0;i < v1.size(); i++)
        cout<<v1.at(i)<<' ';
    cout<<endl;

    //获取第一个元素
    cout<<"第一个元素为: "<<v1.front()<<endl;

    //获取最后一个元素
    cout<<"最后一个元素为: "<<v1.back()<<endl;
}
void test06()//互换容器
{
    //1.基本使用
    cout<<"交换前: "<<endl;
    vector<int> v1;
    for(int i=0;i<10;i++)
        v1.push_back(i);//尾插
    printVector(v1);

    vector<int> v2;
    for(int i=10;i>0;i--)
        v2.push_back(i);//尾插
    printVector(v2);

    cout<<"交换后: "<<endl;
    v1.swap(v2);
    printVector(v1);
    printVector(v2);
    cout<<"-----------"<<endl;
    //实际用途
    //巧用swap可以收缩空间
    vector<int> v;
    for(int i=0;i<10000;i++)
        v.push_back(i);

    cout<<"v的容量为: "<<v.capacity()<<endl;
    cout<<"v的大小为: "<<v.size()<<endl;

    v.resize(3);
    cout<<"v的容量为: "<<v.capacity()<<endl;
    cout<<"v的大小为: "<<v.size()<<endl;

    //巧用swap收缩内存
    vector<int>(v).swap(v);//匿名对象

    cout<<"v的容量为: "<<v.capacity()<<endl;
    cout<<"v的大小为: "<<v.size()<<endl;
}
void test07()//预留空间
{
    vector<int> v;

    //利用reserve预留空间
    v.reserve(100000);

    int num = 0;//统计开辟次数
    int * p = NULL;

    for(int i=0;i<100000;i++)
    {
        v.push_back(i);

        if(p != &v[0])
        {
            p = &v[0];
            num++;
        }
    }

    cout<<"num = "<<num<<endl;
    }
int main()
{
    //test01();//构造函数
    //test02();//赋值
    //test03();//容量和大小
    //test04();//插入和删除
    //test05();//数据存取
    //test06();//互换容器
    test07();//预留空间
    return 0;
}


分享 String用法

果子
20天前
#include<iostream>
#include<string>
using namespace std;
void test01()//构造函数
{
    string s1;
    cout<<"s1 = "<<s1<<endl;

    const char * str="hello world!";
    string s2(str);
    cout<<"s2 = "<<s2<<endl;

    string s3(s2);
    cout<<"s3 = "<<s3<<endl;

    string s4(10,'a');
    cout<<"s4 = "<<s4<<endl;
}
void test02()//string 赋值操作
{
    string s1;
    s1="hello";
    cout<<"s1 = "<<s1<<endl;

    string s2;
    s2=s1;
    cout<<"s2 = "<<s2<<endl;

    string s3;
    s3='a';
    cout<<"s3 = "<<s3<<endl;

    string s4;
    s4.assign("hello c++");
    cout<<"s4 = "<<s4<<endl;

    string s5;
    s5.assign("hello c++",5);
    cout<<"s5 = "<<s5<<endl;

    string s6;
    s6.assign(s5);
    cout<<"s6 = "<<s6<<endl;

    string s7;
    s7.assign(10,'w');
    cout<<"s7 = "<<s7<<endl;

}
void test03()//字符串拼接
{
    string s1;
    string s2;
    s1.assign("hello ");
    s2.assign("c++");
    //s1+=s2;
    //s1+="world";
    //s1+='w';
    //s1.append("world",2);
    //s1.append(s2);
    //s1.append(s2,1);
    cout<<"s1 = "<<s1<<endl;

}
void test04()//字符串查找
{
    string str1="abcdefgde";

    int pos = str1.find("de");

    if(pos == -1)
        cout<<"未找到字符串"<<endl;
    else
        cout<<"找到字符串,pos = "<<pos<<endl;

    //rfind
    //rfind从右往左查找 find从左往右查找
    pos=str1.rfind("de");

    cout<<"pos ="<<pos<<endl;

}
void test05()//字符串替换
{
    string str1 = "abcdefg";

    //从1号位置起3个字符替换为“1111”
    str1.replace(1,3,"1111");

    cout<<"str1 = "<<str1<<endl;
}
void test06()//字符串比较
{
    string str1 = "xello";
    string str2 = "hello";

    int ret = str1.compare(str2);

    if(ret == 0)
        cout<<"str1 等于 str2"<<endl;
    else if(ret > 0)
        cout<<"str1 大于 str2"<<endl;
    else 
        cout<<"str1 小于 str2"<<endl;
}
void test07()//字符串存取
{
    string str1 = "hello";
    //通过[]访问
    for(int i = 0; i < str1.size(); i++)
        cout<<"str["<<i<<"] = "<<str1[i]<<endl;

    cout<<"--------------"<<endl;
    //通过at方式访问
    for(int i = 0; i < str1.size(); i++)
        cout<<"str["<<i<<"] = "<<str1.at(i)<<endl;
    cout<<"--------------"<<endl;
    //修改
    str1[0]='x';
    cout<<"str1[0] = "<<str1[0]<<endl;

    str1.at(0)='h';
    cout<<"str1[0] = "<<str1.at(0)<<endl;
}
void test08()//字符串插入和删除
{
    string s1="hello";

    //插入
    s1.insert(1,"111");
    cout<<"s1 = "<<s1<<endl;

    s1.insert(1,3,'a');
    cout<<"s1 = "<<s1<<endl;

    //删除
    s1.erase(1,3);
    cout<<"s1 = "<<s1<<endl;
    s1.erase(1,3);
    cout<<"s1 = "<<s1<<endl;
}
void test09()//子串
{
    string str = "abcdef";
    string sub=str.substr(1,3);
    cout<<"sub = "<<sub<<endl;

    //实用操作
    string email = "zhangsan@sina.com";

    //从邮件地址中 获取 用户名信息
    int len=email.find('@');
    sub = email.substr(0,len);
    cout<<"用户名 = "<<sub<<endl;
}
int main()
{
    //test01();//构造函数
    //test02();//赋值操作
    //test03();//拼接
    //test04();//查找
    //test05();//替换
    //test06();//比较
    //test07();//存取
    //test08();//插入和删除
    test09();//子串
    return 0;
}


活动打卡代码 AcWing 154. 滑动窗口

果子
2个月前
#include<iostream>

using namespace std;

const int N=1e6+10;

int n,k;

int a[N],q[N],hh=0,tt=-1;//这里q[],[]应该是k的最大值,题目没给出默认跟n一样

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

    for(int i=0;i<n;i++)
    {
        // 判断队头是否滑出窗口
        if(hh<=tt && i-k+1>q[hh])hh++;
        while(hh<=tt && a[q[tt]]>=a[i])tt--;
        q[++tt]=i;
        if(i>=k-1)printf("%d ",a[q[hh]]);
    }
    puts("");

    hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
        // 判断队头是否滑出窗口
        if(hh<=tt && i-k+1>q[hh])hh++;
        while(hh<=tt && a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i>=k-1)printf("%d ",a[q[hh]]);
    }
    puts("");
    return 0;
}