看试卷

摘要:
考试结束后,作为班主任的T老师需要为n名学生更换试卷。T老师有一个习惯,就是按照学生编号的顺序看试卷,所以每次考试前T老师都需要安排好试卷的顺序。所以他让你把纸分成小摞,这样她就可以通过对每一摞单独分类来对整摞纸进行分类。确保试卷上的学生编号为0…n-1。N˂=100000输出一个数字,表示纸张的最大堆叠数。样本输入Copy543210样本输出Copy1提示1。样本解释说,将试卷分成2堆或更多块,无法获得所需的结果。
在一次考试之后,作为班主任的T老师需要给n个学生改卷子,T老师有个习惯,就是按学号的先后来看卷子,所以T老师每次看卷子之前都需要给卷子排好先后次序再改。
但是因为T老师的空闲时间很短,所以他想尽量把这个排序的任务分成多次来做。因此他请你将卷子分成一小叠一小叠的(但不打乱卷子现有顺序),使得她只需要对每一叠分别排序,就能将整堆卷子排序。
初始的卷子次序为a[i],请问你最多能把卷子分成多少小叠。
保证卷子上面的学号为0...n-1的一个排列。

输入

第一行一个数n;
第二行n个数表示a[i],以空格隔开。
n<=100000

输出

输出一个数,表示最多分出多少叠卷子。

样例输入 Copy

5
4 3 2 1 0

样例输出 Copy

1

提示

1. 样例解释
将卷子分成2叠或者更多块,都无法得到所需的结果。
例如,分成 [4, 3], [2, 1, 0] ,排序得到的结果是 [3, 4, 0, 1, 2],这不是有序的数组。
2. 数据范围
对于20%的数据,1≤n≤20;
对于53%的数据,1≤n≤1000;
对于60%的数据,1≤n≤2000;
对于100%的数据,1≤n≤100000。
 
题目解析:因为a0...n-1的一个排列。因此,一段区间[i,j]可以单独分块排序,一定满足前j个值为1-j如何快速判断条件是否成立呢?可以通过判断(a_1-a_j)中的最大值是否为j来做,因此只要记录前缀最大值就好,复杂度O(n)
AC代码:
看试卷第1张看试卷第2张
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e5+10;
int main()
{
    int t,h;
    cin>>t;
    int ans,sum=0;
    for(int i=0;i<t;i++){
        cin>>h;
        ans=max(ans,h);
        if(ans==i){
            sum++;
        }
    }
    printf("%d
",sum);
    return 0; 
}
View Code

AC代码2:

看试卷第3张看试卷第4张
#include <bits/stdc++.h> using namespace std;
int main() 
{
    int n,max=0,ans=0,num; 
    cin>>n;
    for(int i = 0; i < n; i++){ 
        cin>>num;
        max = max > num ? max : num; 
        ans += max == i;
    }    
    cout << ans << endl; 
    return 0;
}
View Code

免责声明:文章转载自《看试卷》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇从800个GPU训练几十天到单个GPU几小时,看神经架构搜索如何进化喂竹鼠下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

关于富勒富勒旗舰店 天猫Tmall.com

关于富勒-富勒旗舰店- 天猫Tmall.com Fuhlen(富勒)品牌简介 Fuhlen(富勒)是全欧洲第二大电脑公司-德国FTS技术解决中心技术合作之下,并聘请全球顶级设计公司-德国die:haptiker GmbH公司精心设计的电脑外设品牌。 “fühlen”在德语中的是“感受、感知”的含义,与英文中的“feel”同意,旨在“感知现在,创造未来”。精...

这三天低效率开发的总结,我都做了些什么啊?

4月15日 一大早起来,本来想测试一下服务端程序。把二手笔记本的ubuntu打开,把自己原来笔记本的windows打开。客户端运行在windows上,服务端运行在ubuntu上。测试了一下发现服务端发给客户端的数据通道地址不对。在ubuntu上改了一下服务端代码。然后向把代码推送到GitHub上,发现不能推送。Git还是使用不熟练。百度了一下,折腾好一会搞...

Debian下Fcitx的简单安装与配置

Fcitx的简单安装与配置 个人认为Fcitx是Linux下最好用的输入法,呵呵,其实这只是一个个人的习惯问题,至少个人觉得是相当的好用。在这里简单记录一下在Debian下Fcitx的简单安装与配置。1 安装Fcitx# apt-get install fcitx2 配置一般来说我们都是希望在系统启动的时候可以自动启动输入法。这时我们可以在/etc/X11...

您敢对Linux说不吗?

本文是Ziff Davis Internet的资深编辑Steven J. Vaughan-Nichols就Linux和Windows的比较所作的精彩论述。 我爱Linux。我的服务器上运行的是它,我的桌面电脑上运行的是它,我的娱乐中心上运行的还是它。在我的娱乐中心里,Linux支撑着我的HDTV TiVo和D-Link DSM-320媒体播放机,其中后者将...

Effective C++学习笔记之第四章(1)

chapter 4:设计与声明 item18:让接口容易被正确使用,不易被误用 理想情况下应该是如果能编译通过,那么接口一定能实现你想要的,否则就不能编译 假设正在设计一个表示时间数据的类的构造函数:Date(int month, int day, int year);这样会出现两个问题,一是传参的顺序不对,而是所传参数的取值范围不对。 1)用户在传参的...

小米资深工程师瞿晋萍(男):米聊服务器的技术选型和架构设计

小米资深工程师瞿晋萍:米聊服务器的技术选型和架构设计 - 资讯频道 - CSDN.NET 小米资深工程师瞿晋萍:米聊服务器的技术选型和架构设计 2012-07-07 11:04 |238次阅读 | 来源:CSDN 【已有0条评论】发表评论 关键词:小米 | 作者:张祺 | 收藏这篇资讯 2012年技术嘉年华于7月7日-8日在杭州海外海皇冠假日酒店拉...