Description

科學(xué)家溫斯頓在一張超長的白紙上寫下了兩行數(shù)，每一行數(shù)有N個(gè)。
但他寫完后覺得看起來有點(diǎn)不和諧。他希望重新編排，使得每一行數(shù)中沒有相同的數(shù)。
他每次可以調(diào)換同一列的兩個(gè)數(shù)。
請幫他找到操作次數(shù)最少的方案。

Input

第一行一個(gè)正整數(shù)N，代表每一行數(shù)的個(gè)數(shù)。
第二第三行每行N個(gè)數(shù)，代表第一行與第二行的數(shù)值。

Output

第一行一個(gè)整數(shù)，表示最少的操作次數(shù)。數(shù)據(jù)保證合法的操作是存在的。

Sample Input

9
2 5 5 2 7 4 7 3 9
1 6 8 4 6 3 9 1 8

Sample Output

3

Hint

對于樣例數(shù)據(jù)，只需調(diào)換1，3，5列即可。

Data Constraint

設(shè)字符串的長度為N。
Subtask1[30pts]:N<=500
Subtask2[30pts]:N<=5000
Subtask3[40pts]:N<=50000
數(shù)值Xi滿足1<=X<=100000

Solution

• 可以明顯得到同一個(gè)數(shù)不可能出現(xiàn) 3 次或以上，否則無解。

• 如果同一個(gè)數(shù)出現(xiàn)在同一側(cè)（設(shè)其出現(xiàn)在 X 列和 Y 列），那么 X 列與 Y 列之中有且只有一列要調(diào)換；

• 如果同一個(gè)數(shù)出現(xiàn)在不同一側(cè)（設(shè)其出現(xiàn)在 X 列和 Y 列），那么要么均不調(diào)換，要么均調(diào)換。

• 我們把每一列看作一個(gè)點(diǎn)，這樣的關(guān)系用邊連起來，那么連通塊內(nèi)相互影響，而連通塊之間
  是相互獨(dú)立的。

• 所以分別處理每一個(gè)連通塊：隨機(jī)確定一列換不換，那么連通塊內(nèi)其余的狀態(tài)都會(huì)被確定。

• 我們只需選擇操作數(shù)少的即可。

Code

#include<cstdio> using namespace std; const int N=50001; int n,ans,sum,tot; int first[N],next[N<<1],en[N<<1],w[N<<1]; int a[N<<1],b[N<<1],f[N]; bool bz[N],bz1[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void dfs(int x) {sum+=f[x];bz[x]=true;for(int i=first[x];i;i=next[i])if(!bz[en[i]]){f[en[i]]=(f[x]+w[i])&1;dfs(en[i]);}f[x]=0; } inline void dfs1(int x) {sum+=f[x];bz1[x]=true;for(int i=first[x];i;i=next[i])if(!bz1[en[i]]){f[en[i]]=(f[x]+w[i])&1;dfs1(en[i]);} } int main() {n=read();for(int i=1;i<=n;i++){int x=read();if(!a[x]) a[x]=i; else{insert(i,a[x],1);insert(a[x],i,1);}}for(int i=1;i<=n;i++){int x=read();if(a[x]){insert(i,a[x],0);insert(a[x],i,0);}elseif(!b[x]) b[x]=i; else{insert(i,b[x],1);insert(b[x],i,1);}}for(int i=1;i<=n;i++)if(!bz[i]){sum=f[i]=0;dfs(i);int k=sum;sum=0,f[i]=1;dfs1(i);if(k<sum) sum=k;ans+=sum;}printf("%d",ans);return 0; } 與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的JZOJ 4675. 【NOIP2016提高A组模拟7.21】Double-row的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。