http://acm.pku.edu.cn/JudgeOnline/problem?id=1147
開始我是這樣猜測的:
輸入的最后一列的元素是第一行出現的元素,所以直接排序輸出即可.
WA
研究了n久,原來是題意理解有問題.,,
這句話很詭異 Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’'
經過研究,發現題意原來是這樣的 : 1.所有行都是經過某一行的rotated versions 2.即上面這句話的理解:將所有的rotated versions 排序.... 3.由1和2,所以行的順序和生成rotated versions 的順序相比,是混亂的....
注意到有一點是確定的,同一行中最后一個數和第一個數的關系.
方法: 因為是經過按照row排序的,所以第一列肯定是排好序.第一列和最后一列對照,可得出以上說的"混亂"的順序,保存在next數組里. 最后按照next數組的順序排列input數據...
這題費了我一個半小時,網上也找不到任何代碼和算法,確實是經典啊~~
a[] 放輸入數據,即最后一列
b[]放第一列
next[]是根據這兩列比較得到的順序
輸出的時候 注意這個通用的小技巧
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]);
}
}