[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;
}
0 条评论