优先队列

佚名 6年前 (2019-04-14) 随笔 1629人围观抢沙发百度已收录

链接：https://ac.nowcoder.com/acm/contest/558/E
来源：牛客网

区间时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小猫在研究序列。小猫在研究单调性。给定一个长度为N的序列a1,a2,…,aN，请你选出一个最长的区间[l,r](1≤l≤r≤N)，满足al≤al+1≤…≤ar。如果有多个，请输出l最小的。

输入描述:

第一行一个正整数T，表示数据组数。

每组数据的第一行一个正整数N。

接下来一行N个正整数a1,a2,…,aN。

输出描述:

T行，每行两个正整数l,r，表示选出的区间。

示例1

输入

复制

输出

复制

备注:

1≤T,N,a

≤1000

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

struct node{
    int l,r,len;
    friend bool operator < (const node &a,const node &b){
        if(a.len!=b.len){
            return a.len<b.len;
        }else{
            return a.l>b.l;
        }
    }
};

int t,n,a[1000+3];

int main(){
    scanf("%d",&t);
    while(t--){
        priority_queue<node>q;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        int cnt=n;
        int l=1,r;
    //    printf("!!  ");
        while(cnt>0){
            node temp;
            temp.len=1; 
            temp.l=l;
            temp.r=l;
            for(int i=l+1;i<=n;i++){
                if(a[i-1]<=a[i]){
                    temp.len++;
                    temp.r=i;
                }else{
                    l=i;
                    break;
                }
            }
            cnt-=temp.len;
            q.push(temp);
        }
        node temp1=q.top();
        printf("%d %d\n",temp1.l,temp1.r);
    }
    return 0;
}