題目

題目描述
2n2n soldiers are standing in a double-row. They have to be rearranged, so that there are no equally tall soldiers in each row - then we shall say, that the soldiers are set up properly.

A single operation consists in swapping two soldiers who occupy the same position (but in different rows). Your task is to determine the minimum number of swaps necessary to set the soldiers up properly.

Example:

There is a double-row of 1818 soldiers in the figure. Arrows indicate the swaps that rearrange the soldiers in a proper way.

TaskWrite a programme that:

reads from the standard input the number and heights of soldiers, as they stand initially,determines the minimum number of swaps (of soldiers standing on the same position in different rows) necessary to set up soldiers properly,writes the result to the standard output.

一句話題意By Scarlet：2n2n個數站成兩排（每個數在2n2n個數中最多出現兩遍），一次操作可以交換任意一列中兩個數，求使每行數不重復的最少操作數。

輸入格式
In the first line of the input there is one integer nn, 1\le n\le 50\ 0001≤n≤50 000. In each of the two rows there are nn soldiers standing. In each of the following two lines there are nn positive integers separated by single spaces. In the second line there are numbers x_1,x_2,\cdots,x_nx
1
?
,x
2
?
,?,x
n
?
, 1\le x_i\le 100\ 0001≤x
i
?
≤100 000; x_ix
i
?
denotes the height of the ii’th soldier in the first line. In the third line there are numbers y_1,y_2,\cdots,y_ny
1
?
,y
2
?
,?,y
n
?
, 1\le y_i\le 100\ 0001≤y
i
?
≤100 000; y_iy
i
?
denotes the height of the ii’th soldier in the second line.

It is guaranteed that in the instances from the test data it is possible to set up soldiers properly.

輸出格式
In the first and only line of the standard output one integer should be written - the minimum number of swaps necessary to set up soldiers properly.

題意翻譯
題目描述

有2n個士兵站成兩排，他們需要被重新排列，以保證每一排里沒有同樣高的士兵——這樣我們就說，士兵們被合理地安排了位置。 每次操作可以交換兩個在同一位置（但不在同一排）的士兵。你的任務是用最少的操作來確保士兵們被合理地安排了位置。 例如： 有18個士兵站成兩排，箭頭標明了重新安排士兵位置的正確方式（圖飛了?）。 寫一個這樣的程序： 讀入n與士兵的身高，以及他們最初所站的位置，確保以最小的交換（站在同一位置的不同排的士兵）的次數來合理地安排士兵的位置，輸出操作數。

輸入格式

第一行為一個整數n（1<=n<=50000），接下來的兩行每行有n個數表示每行站著的n個士兵的身高（1<=士兵的身高<=100000）。 數據保證你能夠合理地安排士兵的位置（即每個數在2n個數中最多出現兩次）。

輸出格式

只有一行，輸出最小操作數。 翻譯貢獻者UID：57699

輸入輸出樣例
輸入 #1復制
9
2 5 5 2 7 4 7 3 9
1 6 8 4 6 3 9 1 8
輸出 #1復制
3

思路

腦力鍛煉題
如果兩個相同的數在不在同一行，給兩個數所在的列的編號連一條邊權為0的邊
如果兩個相同的數在同一行，給兩個數所在的列的編號連一條邊權為1的邊
給每個聯通塊的點黑白染色（1邊連接的點顏色相反，0邊連接的點顏色相同），答案就是sigma(每個聯通塊的min(black,white))

代碼

#include<bits/stdc++.h> using namespace std; int pos[100010][2]; int n,tmp0; struct E {int v,w;E *next; }*h[50010],pool[100010]; int top; void add(int u,int v,int w) {E *tmp=&pool[top++];tmp->v=v;tmp->w=w;tmp->next=h[u];h[u]=tmp;E *pmt=&pool[top++];pmt->v=u;pmt->w=w;pmt->next=h[v];h[v]=pmt; } int vis[50010],col[50010],cntc[2],cnt,ans; void dfs(int u) {vis[u]=1;cntc[col[u]]++;for(E *tmp=h[u];tmp;tmp=tmp->next){if(!vis[tmp->v]){col[tmp->v]=col[u]^tmp->w;dfs(tmp->v);}} } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&tmp0);if(pos[tmp0][0])pos[tmp0][1]=i;else pos[tmp0][0]=i;}for(int i=1;i<=n;i++){scanf("%d",&tmp0);if(pos[tmp0][0])pos[tmp0][1]=-i;else pos[tmp0][0]=-i;}for(int i=1;i<=100000;i++){if(pos[i][0]&&pos[i][1]){add(abs(pos[i][0]),abs(pos[i][1]),!((pos[i][0]>0)^(pos[i][1]>0)));}}for(int i=1;i<=n;i++){if(!vis[i]){cntc[0]=cntc[1]=0;dfs(i);ans+=min(cntc[0],cntc[1]);}}printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的[POI2005]DWU-Double-row的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。