为什么都能想到建图，感觉建图策略很不明显，本篇题解提供一种学数据结构学傻了的数据结构模拟贪心策略解法。
首先手玩几个样例，发现当有两个同色球位于不同桶顶端时，存在以下几种操作：
1. 两个球，均在桶的上方位置，此时需要有一个空桶才能使得两个球放到同一个桶当中，操作次数为 2。
2. 两个球，一个在桶的上方位置，一个在桶的下方位置，此时把在一号位置的球放在位于二号位置的球的桶中，操作次数为 1。
3. 两个球，均在桶的下方位置，此时可以把两个球放到同一个桶当中，然后得到一个空桶，操作次数为 1。
然后分讨一下是否存在空桶的情况：
但是会存在球都被错开的情况，此时上方的操作无法进行，且一种颜色的球只会在顶端出现一次，如：桶一从上到下存颜色为 $1$，为 $2$ 的球，桶二从上到下存颜色为 $2$，为 $1$ 的球，此时只有存在空桶才能继续操作下去，可以把一个位于桶的上方的球放到空桶当中，然后进行上方的操作，如果还是无法进行，则说明无解。
发现需要维护一种数据结构来维护球有多少在最顶端，支持查询全局最大值，单点修改，并且需要维护不同情况下的策略，这里我采用了线段树。
整体复杂度 $O(n\log n)$
代码实现丑，较上方描述略为复杂，慎看
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int INF=1e18;
struct node{
int f,s;
};//第一个球与第二个球
node a[N];
int zw[N][3];//两次出现的位置
int rk[N][3];//两次出现在上方还是下方
int zd[N][3];//是否在所在桶的顶端
int kt=1;
#define ls u<<1
#define rs u<<1|1
struct sgt{
int l,r,mx,id;
};
sgt tr[N*4];
inline void up(int u){
tr[u].mx=-INF;
if(tr[ls].mx==1){
if(tr[ls].mx>tr[u].mx&&((zd[tr[ls].id][1]==1&&rk[tr[ls].id][1]==1)||(zd[tr[ls].id][2]==1&&rk[tr[ls].id][2]==1))){
tr[u].mx=tr[ls].mx;tr[u].id=tr[ls].id;
}
}
if(tr[ls].mx==2){
if(tr[ls].mx>tr[u].mx&&zd[tr[ls].id][1]==1&&zd[tr[ls].id][2]==1){
tr[u].mx=tr[ls].mx;tr[u].id=tr[ls].id;
}
else if(tr[ls].mx==tr[u].mx&&zd[tr[ls].id][1]==1&&zd[tr[ls].id][2]==1){
if(rk[tr[ls].id][1]+rk[tr[ls].id][2]==4&&rk[tr[u].id][1]+rk[tr[u].id][2]!=4){
tr[u].id=tr[ls].id;
}
else if(kt){
if(rk[tr[ls].id][1]+rk[tr[ls].id][2]==2&&rk[tr[u].id][1]+rk[tr[u].id][2]==3){
tr[u].id=tr[ls].id;
}
}
else{
if(rk[tr[ls].id][1]+rk[tr[ls].id][2]==3&&rk[tr[u].id][1]+rk[tr[u].id][2]==2){
tr[u].id=tr[ls].id;
}
}
}
}
if(tr[rs].mx==1){
if(tr[rs].mx>tr[u].mx&&((zd[tr[rs].id][1]==1&&rk[tr[rs].id][1]==1)||(zd[tr[rs].id][2]==1&&rk[tr[rs].id][2]==1))){
tr[u].mx=tr[rs].mx;tr[u].id=tr[rs].id;
}
}
if(tr[rs].mx==2){
if(tr[rs].mx>tr[u].mx&&zd[tr[rs].id][1]==1&&zd[tr[rs].id][2]==1){
tr[u].mx=tr[rs].mx;tr[u].id=tr[rs].id;
}
else if(tr[rs].mx==tr[u].mx&&zd[tr[rs].id][1]==1&&zd[tr[rs].id][2]==1){
if(rk[tr[rs].id][1]+rk[tr[rs].id][2]==4&&rk[tr[u].id][1]+rk[tr[u].id][2]!=4){
tr[u].id=tr[rs].id;
}
else if(kt){
if(rk[tr[rs].id][1]+rk[tr[rs].id][2]==2&&rk[tr[u].id][1]+rk[tr[u].id][2]==3){
tr[u].id=tr[rs].id;
}
}
else{
if(rk[tr[rs].id][1]+rk[tr[rs].id][2]==3&&rk[tr[u].id][1]+rk[tr[u].id][2]==2){
tr[u].id=tr[rs].id;
}
}
}
}
}
inline void build(int u,int l,int r){
tr[u].l=l;tr[u].r=r;
if(l==r){
tr[u].mx=0;tr[u].id=l;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(u);
}
inline void add(int u,int x,int k){
if(tr[u].l==x&&tr[u].r==x){
tr[u].mx+=k;
return;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid){
add(ls,x,k);
}
if(x>mid){
add(rs,x,k);
}
up(u);
}
struct nd{
int mx,id;
};//最大出现次数，是哪种颜色的球
inline nd mx(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return {tr[u].mx,tr[u].id};
}
int mid=(tr[u].l+tr[u].r)>>1;
nd ans={-INF,0};
if(l<=mid){
nd lt=mx(ls,l,r);
if(lt.mx==1){
if(lt.mx>ans.mx&&((zd[lt.id][1]==1&&rk[lt.id][1]==1)||(zd[lt.id][2]==1&&rk[lt.id][2]==1))){
ans.mx=lt.mx;ans.id=lt.id;
}
}
if(lt.mx==2){
if(lt.mx>ans.mx&&zd[lt.id][1]==1&&zd[lt.id][2]==1) ans=lt;
else if(lt.mx==ans.mx&&zd[lt.id][1]==1&&zd[lt.id][2]==1){
if(rk[lt.id][1]+rk[lt.id][2]==4&&rk[ans.id][1]+rk[ans.id][2]!=4){
ans=lt;
}
if(kt){
if(rk[lt.id][1]+rk[lt.id][2]==2&&rk[ans.id][1]+rk[ans.id][2]==3){
ans=lt;
}
}
else{
if(rk[lt.id][1]+rk[lt.id][2]==3&&rk[ans.id][1]+rk[ans.id][2]==2){
ans=lt;
}
}
}
}
}
if(r>mid){
nd rt=mx(rs,l,r);
if(rt.mx==1){
if(rt.mx>ans.mx&&((zd[rt.id][1]==1&&rk[rt.id][1]==1)||(zd[rt.id][2]==1&&rk[rt.id][2]==1))){
ans.mx=rt.mx;ans.id=rt.id;
}
}
if(rt.mx==2){
if(rt.mx>ans.mx&&zd[rt.id][1]==1&&zd[rt.id][2]==1) ans=rt;
else if(rt.mx==ans.mx&&zd[rt.id][1]==1&&zd[rt.id][2]==1){
if(rk[rt.id][1]+rk[rt.id][2]==4&&rk[ans.id][1]+rk[ans.id][2]!=4){
ans=rt;
}
if(kt){
if(rk[rt.id][1]+rk[rt.id][2]==2&&rk[ans.id][1]+rk[ans.id][2]==3){
ans=rt;
}
}
else {
if(rk[rt.id][1]+rk[rt.id][2]==3&&rk[ans.id][1]+rk[ans.id][2]==2){
ans=rt;
}
}
}
}
}
return ans;
}
#undef ls
#undef rs
signed main(){
// freopen("p1.in","r",stdin);
// freopen("bins.in","r",stdin);
// freopen("bins.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
build(1,1,n);
int ok=0;
for(int i=1;i<=n;i++){
cin>>a[i].f>>a[i].s;
if(a[i].f==a[i].s){
ok++;continue;
}
if(zw[a[i].f][1]){
zw[a[i].f][2]=i;
rk[a[i].f][2]=1;
zd[a[i].f][2]=1;
}
else{
zw[a[i].f][1]=i;
rk[a[i].f][1]=1;
zd[a[i].f][1]=1;
}
if(zw[a[i].s][1]){
zw[a[i].s][2]=i;
rk[a[i].s][2]=2;
}
else{
zw[a[i].s][1]=i;
rk[a[i].s][1]=2;
}
add(1,a[i].f,1);
}
if(ok==n){
cout<<0;
return 0;
}
int ans=0;
for(int i=1;i<=n*2;i++){
nd as=mx(1,1,n);
// cout<<as.mx<<" "<<as.id<<endl;
if(as.mx==2){
int id=as.id;
if(rk[id][1]==1&&rk[id][2]==1){
if(!kt){
cout<<-1;return 0;
}
kt=0;
ans+=2;ok++;
add(1,id,-2);
int w=zw[id][1];
if(zw[a[w].s][1]==w){
zd[a[w].s][1]=1;
}
if(zw[a[w].s][2]==w){
zd[a[w].s][2]=1;
}
add(1,a[w].s,1);
w=zw[id][2];
if(zw[a[w].s][1]==w){
zd[a[w].s][1]=1;
}
if(zw[a[w].s][2]==w){
zd[a[w].s][2]=1;
}
zd[id][1]=0;zd[id][2]=0;
add(1,a[w].s,1);
}
if(rk[id][1]==1&&rk[id][2]==2){
ans++;ok++;
add(1,id,-2);
int w=zw[id][1];
if(zw[a[w].s][1]==w){
zd[a[w].s][1]=1;
}
if(zw[a[w].s][2]==w){
zd[a[w].s][2]=1;
}
zd[id][1]=0;zd[id][2]=0;
add(1,a[w].s,1);
}
if(rk[id][1]==2&&rk[id][2]==1){
ans++;ok++;
add(1,id,-2);
int w=zw[id][2];
if(zw[a[w].s][1]==w){
zd[a[w].s][1]=1;
}
if(zw[a[w].s][2]==w){
zd[a[w].s][2]=1;
}
zd[id][1]=0;zd[id][2]=0;
add(1,a[w].s,1);
}
if(rk[id][1]==2&&rk[id][2]==2){
kt=1;
ans++;ok++;
add(1,id,-2);
zd[id][1]=0;zd[id][2]=0;
}
}
else if(as.mx==1){
if(!kt){
cout<<-1;return 0;
}
ans++;
kt=0;
int id=as.id;
if(rk[id][1]==1){
zd[id][1]=1;
rk[id][1]=2;
int w=zw[id][1];
if(zw[a[w].s][1]==w){
zd[a[w].s][1]=1;
}
if(zw[a[w].s][2]==w){
zd[a[w].s][2]=1;
}
add(1,a[w].s,1);
}
if(rk[id][2]==1){
zd[id][2]=1;
rk[id][2]=2;
int w=zw[id][2];
if(zw[a[w].s][1]==w){
zd[a[w].s][1]=1;
}
if(zw[a[w].s][2]==w){
zd[a[w].s][2]=1;
}
add(1,a[w].s,1);
}
}
else{
cout<<-1;return 0;
}
if(ok==n){
break;
}
}
cout<<ans;
return 0;
}
开发者：Federico2903 & Murasame & quanac-lcx