【贪心】LIS @The 15th Zhejiang Provincial Collegiate Programming Contest E

题意要你构造一个序列，使得该序列的每个位置上的最长上升子序列的长度能构成给定的序列。
构造序列的元素要求还要求满足给定的上下界

solution
我们可以把给出的最长上升子序列的长度按升序排列，长度相同的按下标降序排列。
排完序后第一个数可以贪心的取其下界，同一层（即长度相同）的下标小的取值应该大于等于下标较大的取值
同时取值应该大于前一层下标最大且小于该位置的数

#define IN_LB() freopen("F:\\in.txt","r",stdin)

#define IN_PC() freopen("C:\\Users\\hz\\Desktop\\in.txt","r",stdin)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

struct node {

    int ind,ceil,d,u;

    int ans;

} nd[maxn];

bool cmp(node a,node b) {

    if(a.ceil==b.ceil)return a.ind>b.ind;

    return a.ceil<b.ceil;

}

bool cmp1(node a,node b) {

    return a.ind<b.ind;

}

struct qnode{

    int yuanind,xianind,ceil;

};

queue <qnode> que;

int main() {

//    IN_LB();

    int T;

    scanf("%d",&T);

    while(T--) {

        int n;

        scanf("%d",&n);

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

            nd[i].ind = i;

            scanf("%d",&nd[i].ceil);

        }

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

            scanf("%d%d",&nd[i].d,&nd[i].u);

        }

        sort(nd,nd+n,cmp);

        nd[0].ans = nd[0].d;

        qnode seed;

        seed.yuanind = nd[0].ind;

        seed.xianind = 0;

        seed.ceil = 1;

        while(!que.empty())que.pop();

        que.push(seed);

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

            if(nd[i].ceil==nd[i-1].ceil) {

                if(nd[i].ceil>1){

                    int exind;

                    while(!que.empty()) {

                        if(que.front().yuanind<nd[i].ind) {

                            exind = que.front().xianind;

                            break;

                        }

                        que.pop();

                    }

                    nd[i].ans = max(max(nd[exind].ans+1,nd[i-1].ans),nd[i].d);

                }

                else nd[i].ans = max(nd[i-1].ans,nd[i].d);

                qnode cur;

                cur.yuanind = nd[i].ind;

                cur.xianind = i;

                cur.ceil = nd[i].ceil;

                que.push(cur);

            } else {

                int exind;

                while(!que.empty()) {

                    if(que.front().ceil==nd[i].ceil-1&&que.front().yuanind<nd[i].ind) {

                        exind = que.front().xianind;

                        break;

                    }

                    que.pop();

                }

                nd[i].ans = max(nd[exind].ans+1,nd[i].d);

                qnode cur;

                cur.yuanind = nd[i].ind;

                cur.xianind = i;

                cur.ceil = nd[i].ceil;

                que.push(cur);

            }

        }

        sort(nd,nd+n,cmp1);

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

            printf("%d%s",nd[i].ans,(i==n-1)?"\n":" ");

        }

    }

    return 0;

}

巴特西

【贪心】LIS @The 15th Zhejiang Provincial Collegiate Programming Contest E

最新文章

热门文章