博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Wannafly summer camp Day2I(思维)
阅读量:6803 次
发布时间:2019-06-26

本文共 1389 字,大约阅读时间需要 4 分钟。

#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之间的
//一段想要通过交换得到更多段,需要把中间隔成若干尽可能多的段,两端的段交换,中间的分段,可以使段尽可能的多

转载于:https://www.cnblogs.com/ldudxy/p/9751329.html

你可能感兴趣的文章
Xtrabackup备份恢复常用命令与压缩测试
查看>>
linux运维面试题(一)
查看>>
TFS2008安装图解(详细版本)
查看>>
王家林每日大数据语录Spark篇0016(2015.11.6于南宁)
查看>>
android HOME点击事件的获取
查看>>
2.23——2.25find命令(上中下);2.26 文件名后缀
查看>>
华为服务器的中国梦-当梦想照进现实
查看>>
源码编译安装:隐藏nginx的版本信息
查看>>
python爬虫的常见方式
查看>>
MySQL主从复制(Master-Slave)与读写分离(MySQL-Proxy)实践
查看>>
Linux内核源代码分析-第二章 代码初识-1
查看>>
yslow V2 准则详细讲解
查看>>
沈南鹏:从五大物理定律看新商业法则
查看>>
python学习
查看>>
TCP序列号/确认号详解
查看>>
Linux 链接详解----静态链接实例分析
查看>>
Centos7快速部署CloudStack服务器
查看>>
搭建app自动化测试环境(一)
查看>>
...
查看>>
PPII打不开 更改I.bat
查看>>