【题解】P6676 [COCI2019-2020#2] Slagalica

和大众的做法都不太一样，思路比较简单，实现。。。也比较简单

这题部分分真的能提示很多（为什么洛谷上没有部分分），考场上本来在想怎么拿部分分，然后看了一下部分分，想了一下他们的性质，然后。。。就想出正解了。。。但是不会实现嘤嘤嘤

首先我们看看编号为 $2$ 和 $3$ 的块的性质：他们按规则接在某一个块后面，是不会改变这个块的突出情况的

比如：$5$ 的右边原本是凸出的，我们把 $3$ 接在 $5$ 后面以后，整个块的右边还是凸出的

换句话说，当我们在全部给出的块中去除所有 $2$ 和 $3$ 的块，求出字典序最小的，然后再把 $2$ 和 $3$ 的块插进去就行了

而当 $2$ 和 $3$ 的去掉后，能在中间部分的就只有 $1$ 和 $4$ 了，发现这两个只能交替出现，并且谁先谁后是固定的（可以根据起始块和末尾块的形状确定），然后又由于有一个字典序最小的要求，拍一个序后再放就行了

插 $2$ 和 $3$ 也就简单了，具体的话看代码

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1e5+5;
struct date{
int id,v;
bool vis;
date(){}
date(int ID,int V){
vis=0,id=ID,v=V;
}
};
int n;
int road[MAXN];
priority_queue<int,vector<int>,greater<int> > q[10];
bool check(){
bool flag=0;
for(int i=1;i<=4;i++){
if(q[i].size()){
flag=1;
}
}
return flag;
}
int main(){
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++){
int a,v;
scanf("%d %d",&a,&v);
q[a].push(v);
if(a==1) ans+=2;
if(a==4) ans-=2;
if(a==5) ans++;
if(a==6) ans--;
if(a==7) ans++;
if(a==8) ans--;
}
if(ans!=0){
printf("-1");
return 0;
}
if(q[5].size()){
int step=0;
road[++step]=q[5].top();
q[5].pop();
int l,r;
if(q[7].size()){
l=1;
r=0;
}
else{
l=0;
r=1;
}
while(check()){
while(q[3].size()&&(q[4].size()==l||(q[3].top()<q[4].top()))){
road[++step]=q[3].top();
q[3].pop();
}
if(q[4].size()){
road[++step]=q[4].top();
q[4].pop();
}
while(q[2].size()&&(q[1].size()==r||(q[2].top()<q[1].top()))){
road[++step]=q[2].top();q[2].pop();
}
if(q[1].size()){
road[++step]=q[1].top();
q[1].pop();
}
}
if(q[7].size()){
road[++step]=q[7].top();
}
else{
road[++step]=q[8].top();
}
}
else{
int step=0;
road[++step]=q[6].top();
q[6].pop();
int l,r;
if(q[7].size()){
l=0;
r=1;
}
else{
l=1;
r=0;
}
while(check()){
while(q[2].size()&&(q[1].size()==l||(q[2].top()<q[1].top()))){
road[++step]=q[2].top();
q[2].pop();
}
if(q[1].size()){
road[++step]=q[1].top();
q[1].pop();
}
while(q[3].size()&&(q[4].size()==r||(q[3].top()<q[4].top()))){
road[++step]=q[3].top();
q[3].pop();
}
if(q[4].size()){
road[++step]=q[4].top();
q[4].pop();
}
}
if(q[7].size()){
road[++step]=q[7].top();
}
else{
road[++step]=q[8].top();
}
}
for(int i=1;i<=n;i++){
printf("%d ",road[i]);
}
return 0;
}

最后

以上就是眼睛大皮皮虾为你收集整理的【题解】P6676 [COCI2019-2020#2] Slagalica的全部内容，希望文章能够帮你解决【题解】P6676 [COCI2019-2020#2] Slagalica所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。