http://acm.pku.edu.cn/JudgeOnline/problem?id=1147
開(kāi)始我是這樣猜測(cè)的:
輸入的最后一列的元素是第一行出現(xiàn)的元素,所以直接排序輸出即可.
WA
研究了n久,原來(lái)是題意理解有問(wèn)題.,,
這句話(huà)很詭異 Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’'
經(jīng)過(guò)研究,發(fā)現(xiàn)題意原來(lái)是這樣的 : 1.所有行都是經(jīng)過(guò)某一行的rotated versions 2.即上面這句話(huà)的理解:將所有的rotated versions 排序.... 3.由1和2,所以行的順序和生成rotated versions 的順序相比,是混亂的....
注意到有一點(diǎn)是確定的,同一行中最后一個(gè)數(shù)和第一個(gè)數(shù)的關(guān)系.
方法: 因?yàn)槭墙?jīng)過(guò)按照row排序的,所以第一列肯定是排好序.第一列和最后一列對(duì)照,可得出以上說(shuō)的"混亂"的順序,保存在next數(shù)組里. 最后按照next數(shù)組的順序排列input數(shù)據(jù)...
這題費(fèi)了我一個(gè)半小時(shí),網(wǎng)上也找不到任何代碼和算法,確實(shí)是經(jīng)典啊~~
a[] 放輸入數(shù)據(jù),即最后一列
b[]放第一列
next[]是根據(jù)這兩列比較得到的順序
輸出的時(shí)候 注意這個(gè)通用的小技巧
Source Code
Problem: 1147 User: lnmm
Memory: 104K Time: 152MS
Language: C++ Result: Accepted
Source Code
#include"stdio.h"
int a[3001];
int b[3001];
int next[3001];
bool used[3001];
void main()
{
int n,i,j,k=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==1)k++;
used[i]=false;
}
for(i=1;i<=n-k;i++)
b[i]=0;
for(i=n-k+1;i<=n;i++)
b[i]=1;
for(i=1;i<=n;i++)
{
j=1;
while((b[i]!=a[j])||(used[j]==true))j++;
used[j]=true;
next[i]=j;
}
k=1;
for(i=1;i<=n;i++)
{
k=next[k];
printf("%d ",a[k]);
}
}