首页 > 代码库 > 穷游中国在统题

穷游中国在统题

穷游中国在统题

Description

Travel_poorly队是广工大目前最年轻的金牌队伍,队内成员分别是tmk、YFQ、Maple。这天他们接到教练的order要给新生杯统题,统题是个不轻松的工作,要评估各个题目的难度,设计出一套有梯度的套题,使得做题的情况有区分度。tmk很快想出了解决的办法,他给每道题目都设置了一个难度值,然后按照难度值进行筛选题目,这时候他发现难度值刚开始有可能是无序的,于是他决定要让全部题目都按照难度值从小到大排好序。 这时候YFQ说让他来排序,排序是一个展现算法魅力的过程,他要通过一种有趣的方法来给题目的难度值排序: 首先他把题目划分成很多组,每组的题目都是连续的,例如某一组包含从i到j的题目,那么这一组包含的是第i,i+1,i+2,i+3,...,j题。 这样每道题都属于某一个组,然后他再到组内把题目按照难度值进行从小到大排序。 当每个组内都进行排序之后,最终全部题目的难度值将按照从小到大的顺序排列好。 我们知道每一组里面的题目越多,排序的压力就越大,所以Maple提出一个合理的要求,就是让每个组里面的题目数量尽可能的少,聪明的ACMer,你知道Travel_poorly一共要分出多少个组吗?

Input

第一行是一个整数t ( t<= 10 ),表示有t组数据。在每组数据中: 第一行是一个整数n ( n<=1000 00 ),表示题目的总数; 第二行是n个整数A1,A2,A3...An ( 0<=Ai<= 1000 000 000),表示每道题目的难度值

Output

对于每组数据,输出一个正整数,表示一共要分出多少个组能满足Travel_poorly的要求,每两组样例之间输出一个空行。

Sample Input

2 5 3 2 5 4 6 5 5 4 3 2 1

Sample Output

3 1

 分析:考虑到这样一个事实,若当前这个数及之前的数都小于等于后面的数,则可以开辟一个分组;

   那么预处理ma[i]表示从a[1-i]的最大值,mi[i]表示从a[i+1-n]的最小值;

   ma[i]<=mi[i],ans++,复杂度O(n);

代码:

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]#define sys system("pause")#define intxt freopen("in.txt","r",stdin)const int maxn=1e5+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){    ll x=0;int f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}int n,m,k,t;ll a[maxn],ma[maxn],mi[maxn];bool flag;int main(){    int i,j;    scanf("%d",&t);    while(t--)    {        if(flag)printf("\n");        else flag=true;        scanf("%d",&n);        rep(i,1,n)a[i]=read();        rep(i,1,n)ma[i]=max(ma[i-1],a[i]);        mi[n]=1e18;        for(i=n-1;i>=1;i--)mi[i]=min(mi[i+1],a[i+1]);        ll ans=0;        rep(i,1,n)if(ma[i]<=mi[i])ans++;        printf("%lld\n",ans);    }    //system("Pause");    return 0;}

穷游中国在统题