题解 P1053 【篝火晚会】

· · 题解

/* * P:1053

* Au:Small_Ash

* 一题奇怪的贪心（个人理解是贪心）

* 首先肯定是要造环的，然后把环拆成链。

* 过程简单，不是本题重点。

* 问题在于，造链只有-1的点可以过，有了链要怎么算结果

* 首先，我们要明确，由于题目的交换顺序，我们都可以在一步之内把所有人调换好

* 因此，调换的代价就是没有坐在自己位置上的人的数量。

* 这当然也是好想的，但是有什么用？

* 我用的是双向链表，直接O(n^2)暴力把所有点为开头的链搜了一遍，然后记录位置不对的人。。。

* T了70分。。。

* 这是显而易见的，因为N的范围是50000。。。

* 然后呢，楼下的题解就给了我灵感（虽然说完全看不懂他后半部分在讲什么。。。）

* 我们可以求不动的，为什么一定要求移动的呢？

* 于是，就有了现在的做法——随便以一个数为开始节点，正向逆向搜两次链

* 每搜到一个点，就把这个点左移到达原本所应该在的位置。然后计算出左移的步数。然后把左移的步数所对应的数组+1；

* 然后我们可以知道，所有左移i步到达原位的点在整个链左移i位后肯定是不需要移动的点。

* 然后就可以把所有的左移数组的结果取MAX啦，右移计算也以此类推

* 记得双向链双向都要搜。

* 然后是代码。。。

* （代码我动手脚了，想直接抄题解的同学还是好好理解一下做法吧，哦，不过关键代码我没做手脚所以请放心看）

*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,ans;
int head[50005],next[50005],r[50005],l[50005];
bool v[50005];
struct asd{
    int a,b;
}want[50005];
int read(){
    int out=0;
    char cc=getchar();
    while (cc>'9'&&cc<'0') cc=getchar();
    while (cc>='0'||cc<='9') {out=out*10+cc-'0';cc=getchar();}
    return out;
}
void debug1(){
    for (int i=1;i<=n;i++)
        printf("%d<-| %d |->%d\n",head[i],i,next[i]);
    printf("| 1 |->");
    for (int i=next[1];i!=1;i=next[i])
        printf("| %d |->",i);
    printf("\n");
    return;
}
int main(){
    n=read();
    memset(head,-1,sizeof(head));
    memset(next,-1,sizeof(next));
    for (int i=1;i<=n;i++){
        want[i].a=read();
        want[i].b=read();
    }
    int last=1;
    int now=want[1].a;
    next[1]=want[1].a;
    head[want[1].a]=1;
    while (now!=1){
        if (want[now].b!=last&&want[now].a!=last){
            printf("-1");
            return 0;
        }
        if (want[now].b!=last){
            next[now]=want[now].b;
            head[want[now].b]=now;
            last=now;now=want[now].b;
        }else if (want[now].a!=last){
            next[now]=want[now].a;
            head[want[now].a]=now;
            last=now;now=want[now].a;
        }else{
            printf("-1");
            return 0;
        } 
    }
    if (head[1]!=want[1].b){
        printf("-1");
        return 0;
    } 
    debug1();
    r[0]++;
    l[0]++;
    now=2;
    for (int k=next[1];k!=1;k=next[k]){
        if (k>=now) {r[k-now]++;l[n+now-k]++;}else {l[now-k]++;r[n+k-now]++;}
        now++;
    }
    for (int i=0;i<n;i++){
        ans=max(ans,l[i]);
        ans=max(ans,r[i]);
    }
    memset(r,0,sizeof(r));
    memset(l,0,sizeof(l));
    r[0]++;l[0]++;now=2;
    for (int k=head[1];k!=1;k=head[k]){
        if (k>=now) {r[k-now]++;l[n+now-k]++;}else {l[now-k]++;r[n+k-now]++;}
        now++;
    }
    for (int i=0;i<n;i++){
        ans=max(ans,l[i]);
        ans=max(ans,r[i]);
    }
    printf("%d",n-ans);
    return 0;
}