题解/算法 {C. Goose Goose Duck}

题解/算法 {C. Goose Goose Duck}

@LINK: https://codeforces.com/gym/105184;

令A[N]表示这N个人的区间;
比如答案是[a,b,c,d] 那么他一定满足: A[a].lef <= 0 <= A[a].rig, A[b].lef <= 1 <= A[b].rig, A[c].lef <= 2 <= A[c].rig, …

贪心;
对于最开头的人来说, 令集合S: 满足A[].lef <= 0的区间, 那么我们要选择一个 满足A[].rig >= 0前提下的 最小的A[].rig, 比如说S: [0,0] , [0,1], [0,2] 那么我们选择[0,0], 因为他们都可以放到当前位置 而[0,1], [0,2]他们的rig更大 意味着 后面的位置也可以选择他们 即他们的选择性更大, 我们在当前位置 选择一个选择性最小(即最差)的方案;
更一般的说, 对于当前位置ind (即此时[0,1,2,...,ind-1]这些位置 已经排列好了), 我们要选择一个区间 满足A[].lef <= ind <= A[].rig, 令集合S: 满足A[].lef <= ind的区间, 这些区间里 我们再根据A[].rig从小到大排序 选择一个满足A[].rig >= ind且最小的A[].rig;

注意, 假设说 当前ind位置无解, 那么此时必须break终止流程, 因为位置是连续的 我们规定了ind是表示 [0...,ind-1]位置上都有人 才可以;

注意, 题目没保证lef <= rig, 因此我们假设是存在这样的数据的; 不过 因为我们会判断while( A[].rig < ind){ Heap.pop();} 因此这样情况 不会影响原算法;

void ___Solve_oneTest(){
    int N; cin>> N;
    vector< std::array< int, 3> > A(N);
    FOR_( i, 0, N-1){
        cin>> A[i][0]>> A[i][1];
        A[i][2] = i+1;
    }
    std::sort( A.begin(), A.end());
    using Item_ = std::pair<int,int>;
    std::priority_queue< Item_, std::vector<Item_>, std::greater<> > Heap;
    std::vector<int> ANS;
    int ind = 0;
    FOR_( i, 0, N-1){
        while( ind<N && A[ind][0]<=i){
            Heap.push( {A[ind][1], A[ind][2]});
            ++ ind;
        }
        while( Heap.size() > 0){
            if( Heap.top().first < i){ Heap.pop();}
            else{ break;}
        }
        if( Heap.size() != 0){
            ANS.emplace_back( Heap.top().second);
            Heap.pop();
        }
        else{
            break;
        }
    }
    cout<< ANS.size()<< "\n";
    for( auto i : ANS){
        cout<< i<< " ";
    }
}