天天看点

Wannafly summer camp Day2I(思维)

#include<bits/stdc++.h>

using namespace std;

int a[1000007],b[1000007],c[1000007];

int find_max(int lll,int rrr,int lenn){

    int maxnn=0;

    int summ=0;

    for(int i=lll;i<=rrr;i++){

        maxnn=max(maxnn,c[i]);

        if(maxnn==lenn+i-lll)//这一段可以经过排序满足题意

            summ++;

    }

    return summ;

}

int divide(int l,int r){

    int num=1;

    int len=r-l+1;

    int ll=1;

    for(int i=l;i<=r;i++){

        c[i-l+1]=a[i]-l+1;//对于这一段进行操作,每一段的值都是l到r之间的值,全部减去l-1

    }

    int minn=0;

    for(int i=1;i<=len;i++){

        if(i==1)

            minn=c[1];

        else

            minn=min(minn,c[i]);

        if(minn==len+1-i){//这一段可以和另一半交换

            if(ll==1&&i==len)

                continue;//不可交换串

            if(ll==1||i==len)

                num=max(2,num);//至少可以分成两串

            else{

                int xx=find_max(ll,i,len-i+1);//边上两串交换,中间串尽可能分割

                num=max(xx+2,num);

            }

            ll=i+1;//下一段的左端点

        }

    }

    return num;

}

int main(){

    int n,k;

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

    memset(c,0,sizeof(c));

    scanf("%d%d",&n,&k);

    int maxn=0;

    int sum=0;

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        maxn=max(maxn,a[i]);

        if(maxn==i)//如果最大值和i相等,说明从上一个b[i]+1到i之间的串是可以经过排序满足题意的

            b[i]=i,sum++;//如果sum已经达到k了,就无需去交换操作了

    }

    int ans=sum;

    int flag=1;

    if(ans>=k)

        printf("Yes");

    else{

        for(int i=1;i<=n;i++){

            if(b[i]==i){

                int x=divide(flag,i)-1;//看看每一段中间经过交换操作能多出几段

                ans=max(ans,sum+x);

                flag=i+1;//下一段的左端点

            }

        }

        if(ans>=k)

            printf("Yes");

        else

            printf("Poor Simon");

    }

    return 0;

}

//通过对一段l到r的串进行构造和思考,可以发现满足题意都是l到r之间值都为l到r之间的

//一段想要通过交换得到更多段,需要把中间隔成若干尽可能多的段,两端的段交换,中间的分段,可以使段尽可能的多