洛谷1053 篝火晚會

原題連結

交題記錄

20:28 30'

數組開小了我還能說啥。。。還是WA，這lg。。。

20:30 90'

原因是忘記了序列可以反轉。

20:49 AC

題解

首先是有無解的問題。

考慮極端，佳佳每次都可以交換兩個人，隻是代價大了點。是以隻要關系構成環，就一定有解。

這個dfs搞定

dfs順便計算出可行的序列。這個序列和它反過來的序列都可行（被坑了）。

因為是環，是以斷環為鍊，\(O(n)\)枚舉。

兩個序列\(1,2,...,n\)和\(s_1,s_2,...,s_n\)最少總代價就是\(\sum_{i=1}^{n}s_i!=i\)。可以一次指令把它們全部歸位。

到這裡，算法複雜度為\(O(n^2)\)。

再優化一下：\(s_i!=i\)的情況會出現n-1次，相反\(s_i=i\)隻出現1次。記一個K數組，表示第i條鍊s_i=i出現的次數。答案就是\(max(n-k[i])\)

注意序列可以反轉。

Code

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define lb(o) (o&-o)
#define vd void
typedef long long ll;
il int gi(){
    rg int x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn=50010;
int a[maxn],b[maxn],s[maxn],tot,n,k[maxn],K[maxn];
il vd dfs(int now,int lst){
    s[++tot]=now;
    if(tot==n)return;
    if(a[now]==lst)dfs(b[now],now);
    else if(b[now]==lst)dfs(a[now],now);
    else {puts("-1");exit(0);}
}
int main(){
    n=gi();
    rep(i,1,n)a[i]=gi(),b[i]=gi();
    dfs(1,a[1]);
    rep(i,1,n)++k[(s[i]-i+n)%n],++K[(s[i]+i+n)%n];
    int ans=1e9;
    rep(i,0,n-1)ans=min(ans,n-max(k[i],K[i]));
    printf("%d\n",ans);
    return 0;
}                

轉載于:https://www.cnblogs.com/xzz_233/p/7436371.html