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]);
}
}