佳佳剛進高中，在軍訓的時候，由於佳佳吃苦耐勞，很快得到了教官的賞識，成爲了“小 教官”。在軍訓結束的那天晚上，佳佳被命令組織同學們進行篝火晚會。一共有 n 個同學，編號從 1 到 n 。一開始，同學們按照 1 ， 2 ，……， n 的順序坐成一圈，而實際上每個人都有兩個最希望相鄰的同學。如何下命令調整同學的次序，形成新的一個圈，使之符合同學們的意願，成爲擺在佳佳面前的一大難 題。
佳佳可向同學們下達命令，每一個命令的形式如下：
(b 1 , b 2 ,... b m -1 , b m )
這 裏 m 的值是由佳佳決定的，每次命令 m 的值都可以不同。這個命令的作用是移動編號是 b 1 ， b 2 ，…… b m –1 ， b m 的這 m 個同學的位置。要求 b 1 換到 b 2 的位置上， b 2 換到 b 3 的位置上，……，要求 b m 換到 b 1 的位置上。
執行每個命令都需要一些代價。我們假定如果一個命令要移動 m 個人的位置，那麼這個命令的代價就是 m 。我們需要佳佳用最少的總代價實現同學們的意願，你能幫助佳佳嗎？
【輸入文件】
輸入文件 的第一行是一個整數 n （ 3 <= n <= 50000 ），表示一共有 n 個同學。其後 n 行每行包括兩個不同的正整數，以一個空格隔開，分別表示編號是 1 的同學最希望相鄰的兩個同學的編號，編號是 2 的同學最希望相鄰的兩個同學的編號，……，編號是 n 的同學最希望相鄰的兩個同學的編號。
【輸出文件】
輸出文件 包括一行，這一行只包含一個整數，爲最小的總代價。如果無論怎麼調整都不能符合每個同學的願望，則輸出 -1 。
【輸出樣例】
4
3 4
4 3
1 2
1 2
【輸出樣例】
2
【數據規模】
對於30%的數據，n <= 1000；
對於全部的數據，n <= 50000。
【分析】
據當年參加過NOIP2005的同學回憶道，拿到本題後沒有任何思路，貪心無從下手，動規沒法劃分狀態，搜索又會超時......(所以當年很多人拿了140分，即第一題100，第二題沒有壓縮的動規30分，第三題輸出-1得10分，第四題未寫......)
那麼，爲了拿到一點分，我們先處理最特殊的情況：沒有辦法滿足所有人的意願，即輸入-1的情況，這一點是很好想到的。
設：一共有n個人
l[i]表示第i個人希望成爲其左邊的人的編號
r[i]表示第j個人希望成爲其右邊的人的編號
所有人都能看出來，這是一個環。
4
3 4
4 3
1 2
1 2
如樣例所示，就是這樣的一個環:
1
4 3
2
4 3
2
所以，在讀入後可以做簡要判斷，如果無法構成一個環，就直接輸出-1嘍！！
看代碼：
for (int i=1;i<=n;i++)
{
if ( ( l[l[i]]!=i && r[l[i]]!=i ) || ( l[r[i]]!=i && r[r[i]]!=i ) )
{
printf("-1\n");
}
}
{
if ( ( l[l[i]]!=i && r[l[i]]!=i ) || ( l[r[i]]!=i && r[r[i]]!=i ) )
{
printf("-1\n");
}
}
寫道這裏，已經可以拿10分了～
接下來，就該構造目標狀態了。
在目標狀態中，把誰放在第一位都可以，但爲了下面方便計算，我們把原來的第一個人還放在第一位。
設a[i]是新的位置，即目標狀態
設b[i]是a[i]的倒序鏡像，因爲按題目所述正着成環和倒着成環效果一樣，只需要移動次數最少即可。
a[1]=1//原來一號位還是1號
for (int i=2;i<=n;i++)
{
if (a[i-2]==l[a[i-1]])
a[i]=r[a[i-1]];
else
a[i]=l[a[i-1]];
}然後再把a[i]倒過來放進b[i]數組
{
if (a[i-2]==l[a[i-1]])
a[i]=r[a[i-1]];
else
a[i]=l[a[i-1]];
}然後再把a[i]倒過來放進b[i]數組
現在，目標就很清楚了！就是尋找最小的置換次數，即
應輸出的結果=min{原數列與a[]的最小置換次數，原數列與b[]的最小置換次數}
於是我們有了一種算法，讓新圈和舊圈中的每個數對齊，一共有 n 中可能，統計其中匹配數的最大值，記做 max ，所求即爲 n-max 。
但這個算法是 O(n^2) 的， n=50000 時會超時，需要優化。
我們可以統計新圈中每個數 i 向右移多少位可以和舊圈中的 i 對齊，記做 k ，如果兩個數的 k 相同，那麼右移 k 位後一定都對齊。這樣，只要我們統計出所有 k 出現的次數，從中找出最大值，就是 max 。算法複雜度是 O(n) 的。
需要注意，做完這以後，要講新圈翻轉一下，再做一遍，即對b在做一遍，找出max(a),max(b)中的max，然後輸出n-max即可。
【我的代碼】
#include <iostream>#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef unsigned short int fire[50001];
fire l;//每個人期望的左邊的人
fire r;//每個人期望的右邊的人
fire a;//目標狀態，正序
fire b;//目標狀態，倒序
fire ans;
int n;
void printab()
{
for (int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
for (int i=1;i<=n;i++)
cout<<b[i]<<" ";
}
bool init()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&l[i],&r[i]);
fclose(stdin);
//判斷該是否成環
for (int i=1;i<=n;i++)
{
if ( ( l[l[i]]!=i && r[l[i]]!=i ) || ( l[r[i]]!=i && r[r[i]]!=i ) )
{
return false;
}
}
return true;
}
void compute()
{
int mt=0;
for (int i=1;i<=n;i++)
{
ans[ (a[i]+n-i)%n ]++;
if(mt<ans[(a[i]+n-i)%n])
mt=ans[(a[i]+n-i)%n];
}
memset(ans,0,sizeof(ans));
for (int i=1;i<=n;i++)
{
ans[ (b[i]+n-i)%n ]++;
if(mt<ans[(b[i]+n-i)%n])
mt=ans[(b[i]+n-i)%n];
}
printf("%d\n",n-mt);
return;
}
void construct()
{
//如果成環，則構造目標狀態
a[1]=1;
for (int i=2;i<=n;i++)
{
if (a[i-2]==l[a[i-1]])
a[i]=r[a[i-1]];
else
a[i]=l[a[i-1]];
}
//把a倒過來
for (int i=1;i<=n;i++)
b[n-i+1]=a[i];
//printab();
//cout<<endl;
compute();
return;
}
int main()
{
freopen("fire.in","r",stdin);
freopen("fire.out","w",stdout);
if(init())
construct();
else
printf("-1\n");
fclose(stdout);
return 0;
}
正在连接评测机...
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 10 | 0.000 s | 760 KB | 0 |
| 2 | 正确 | 10 | 0.001 s | 760 KB | 0 |
| 3 | 正确 | 10 | 0.043 s | 760 KB | 0 |
| 4 | 正确 | 10 | 0.030 s | 760 KB | 0 |
| 5 | 正确 | 10 | 0.030 s | 760 KB | 0 |
| 6 | 正确 | 10 | 0.030 s | 760 KB | 0 |
| 7 | 正确 | 10 | 0.030 s | 760 KB | 0 |
| 8 | 正确 | 10 | 0.031 s | 760 KB | 0 |
| 9 | 正确 | 10 | 0.029 s | 760 KB | 0 |
| 10 | 正确 | 10 | 0.000 s | 760 KB | 0 |
运行时间 0.224 s
平均内存使用 760 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
沒有留言:
張貼留言