题解 P1053 【篝火晚会】

yy1695651 · 2018-09-27 12:41:44 · 题解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 50000 + 10;

#if 0
//此题将关系换转化为目标链
//并且判断目标链是否成立，是继续，否输出-1
//转移方法理解
//初始 1 2 3 4 5
//目标 1 3 4 2 5
//     1 _ 4 2 5, 3 取出
//     1 _ 3 2 5, 4 取出
//     1 _ 3 4 5, 2 取出
//     1 2 3 4 5 放入2, 成功
//所以转换命令即为(3, 4, 2)
//有几个与初始位置不同位置的点就要消耗一点代价

//初始 1 2 3 4
//目标 4 3 2 1
//消耗代价为4
//这种情况就是要反着跑
//初始 4 3 2 1
//消耗代价为0
//(因为你只计算了一种方向的环，但环可以有两种方向，可理解为顺时针、逆时针两种)
//到这里可以枚举以n个不同节点为开头，暴力计算，复杂度O(n^2)

//O(n)做法
//初始链   1 2 3 4 5 6
//目标链   4 2 3 1 5 6
//差值      3 0 0 3 0 0
//差值是看这个值向右(或向左)(单个方向)以多少位，才到达初始链
//这个差值，无论环如何旋转，差值相等的还是相等，不等的还是不等
//所以要求的最值就是让差值相同最多的通过旋转，使它们的差值都变为0
//最终要换的都是除这些差值相同点以外的所有点
#endif

int n, B[N], ct, spin1[N], spin2[N];
//spain1记录初始链为1 2 3...的链，差值的个数
//spain2记录初始链为n n-1 n-2...的链，差值的个数
bool vis[N];
struct node {int a, b;}A[N];

bool check(int x){
    B[++ct] = x;
    vis[x] = true;
    if (ct == n) return true;
    if (vis[A[x].a] == false){
        return check(A[x].a);
    }
    if (vis[A[x].b] == false){
        return check(A[x].b);
    }
    return false;
}

int main(){
    //freopen("fire.in", "r", stdin);
    //freopen("fire.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d %d", &A[i].a, &A[i].b);
    }
    if (check(1) == false){
        printf("-1");
        return 0;
    }
    int ans = 0x7FFFFFFF;
    int mx1 = 0, mx2 = 0;;
    for (int i = 1; i <= ct; i++){
        int pos = B[i], len = (i + n - pos) % n;
        spin1[len]++;
        mx1 = max(mx1, spin1[len]);
        pos = (n - B[i]) % n + 1;
        len = (i + n - pos) % n;
        spin2[len]++;
        mx2 = max(mx2, spin2[len]);
    }
    ans = min(ans, min(n - mx1, n - mx2));
    printf("%d", ans);
    return 0;
}