NC16656. [NOIP2005]篝火晚会
描述
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：(b1, b2,... bm -1, bm)这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，……bm -1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？
输入描述
第一行是一个整数n（3<=n<=50000），表示一共有n个同学。
其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。
输出描述
包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。
示例1
输入:
4 3 4 4 3 1 2 1 2
输出:
2
C++14(g++5.4) 解法, 执行用时: 51ms, 内存消耗: 1508K, 提交时间: 2019-09-16 15:50:00
#include<iostream>
using namespace std;
int i, j, m, n, temp;
int a[50001], x[50001], y[50001];
int gs[50001], gs2[50001];
int main() {
cin >> n;
for(i=1; i<=n; i++) cin >> x[i] >> y[i];
a[1] = 1, a[2] = x[1];
for(i = 3; i <= n; i++) {
if(x[a[i-1]] == a[i-2]) a[i] = y[a[i-1]];
else a[i] = x[a[i-1]];
}
int le, ri;
for(i = 1; i <= n; i++) {
le = i-1;
ri = i+1;
if(!le) le = n;
if(ri == n+1) ri=1;
if((x[a[i]] != a[ri] || a[le] != y[a[i]]) && (y[a[i]] != a[ri] || a[le] != x[a[i]])) {
cout<<-1;
return 0;
}
}
int dis1, dis2;
for (i = 1; i <= n; i++) {
dis1 = (a[i]-i+n)%n;
dis2 = (a[i]+i-1)%n;
gs[dis1]++;
gs2[dis2]++;
}
int ans=0;
for (i = 0; i < n; i++) {
if (ans < gs[i]) ans = gs[i];
if (ans < gs2[i]) ans = gs2[i];
}
cout << n-ans;
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 38ms, 内存消耗: 1420K, 提交时间: 2022-11-13 11:21:06
#include<bits/stdc++.h>
#define N 1000001
using namespace std;
int l[N],r[N],a[N],c[N],d1[N],d2[N],n,sum;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
a[n]=l[1],a[1]=1,a[2]=r[1];
for(int i=3;i<n;i++){
if(a[i-2]==l[a[i-1]])a[i]=r[a[i-1]];
else if(a[i-2]==r[a[i-1]])a[i]=l[a[i-1]];
else {puts("-1");return 0;}
}
for(int i=1;i<=n;i++)d1[(i-a[i]+n)%n]++,d2[(a[i]+i+n)%n]++;
for(int i=0;i<=n*2;i++)sum=max(sum,max(d1[i],d2[i]));
printf("%d",n-sum);
}