[ICPC2019 WF]Azulejos

题目链接：https://codeforces.com/gym/102511/problem/A

题目描述

给你两种瓷砖 a,b，每种瓷砖有 n 块，每块瓷砖有两个属性：高度 h 和价值 p。

现在要求你把这些瓷砖重新排成两行（2\times n）。前一行放瓷砖 b，后一行放瓷砖 a

要求从左到右 p 递增（单调不减），对于任意一个位置 i，后面的瓷砖要比前面的瓷砖高。

求一种方案或输出无解。

n\le 5\times 10^5。

Solution

首先考虑两层瓷砖必须按照 p 递增排序，排序以后 p 相同的瓷砖可以任意交换。

那么考虑用 set 分别维护 a 和 b 瓷砖。对于 p 相同的瓷砖，以 h 为关键字，从大到小维护。

在这里，必须要用 size 小的集合 去匹配 size 大的集合。

当我们在维护当前的 p 时（只能维护 p 相同的元素），size 大的集合里的元素不一定能与 size 小的的集合里的元素匹配上。而反过来则一定能匹配上。

解释：假定当前 a 瓷砖的集合 size 小，当前集合维护的元素的 p 均为 p_0

因为 a 的集合必定比 b 集合先匹配完，所以当 a 集合匹配结束以后，a 集合又会维护 p>p_0 的一系列 a 元素（记作 p_1） 。

故 b 集合中的元素，既有可能与 p=p_0 的元素匹配，又有可能与 p=p_1 的元素匹配。

PS：multiset 的 erase() 如果传值进去，会删除所有这个值的元素。。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int a[N],n;
pair<int,pair<int,int> > p_p[N],n_p[N];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        int y;
        scanf("%d",&y);
        n_p[i]=make_pair(a[i],make_pair(y,i)); 
    }
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        int y;
        scanf("%d",&y);
        p_p[i]=make_pair(a[i],make_pair(y,i)); 
    }
}
void solve(){
    sort(p_p+1,p_p+1+n);
    sort(n_p+1,n_p+1+n);
    multiset<pair<int,int> > p_s,n_s;
    multiset<pair<int,int> >::iterator p_it,n_it;
    vector<int> p_ans(n),n_ans(n);
    int p_idx=1,n_idx=1;
    for(int i=0;i<n;++i){
        if(p_s.empty()){
            p_s.insert(p_p[p_idx].second);
            while(p_idx+1<=n&&p_p[p_idx].first==p_p[p_idx+1].first){
                p_idx++;
                p_s.insert(p_p[p_idx].second);
            }
            p_idx++;
        }
        if(n_s.empty()){
            n_s.insert(n_p[n_idx].second);
            while(n_idx+1<=n&&n_p[n_idx].first==n_p[n_idx+1].first){
                n_idx++;
                n_s.insert(n_p[n_idx].second);
            }
            n_idx++;
        }
        if(p_s.size()>n_s.size()){
            n_it = n_s.begin();
            p_it = p_s.lower_bound(make_pair((*n_it).first,0));
            if(p_it==p_s.begin()){
                puts("impossible");
                return ;
            }
            p_it = prev(p_it);
            p_ans[i] = (*p_it).second;
            n_ans[i] = (*n_it).second;
            p_s.erase(*p_it);
            n_s.erase(*n_it);
        }
        else{
            p_it = p_s.begin();
            n_it = n_s.upper_bound(make_pair((*p_it).first,n+1));
            if(n_it==n_s.end()){
                puts("impossible");
                return ;
            }
            p_ans[i] = (*p_it).second;
            n_ans[i] = (*n_it).second;
            p_s.erase(*p_it);
            n_s.erase(*n_it);
        }
    }
    for(int i=0;i<n;++i)
        printf("%d ",n_ans[i]);
    puts("");
    for(int i=0;i<n;++i)
        printf("%d ",p_ans[i]);
}
int main(){
    init();
    solve();
    return 0;
}