首先对于一个按行向量排序的循环矩阵，任意两列都是一一对应的关系，于是我们只需要找到每行第一列和最后一列的对应关系就行了
结论1 : 第一行就是最后一行排序的结果
结论2 ：这个关系是一一对应的，而且对应后的逆结果便是原序列按照字典序第一关键字，位置第二关键字排序之后的位置
这样暴力sort可以解决，然后还可以高大上的用基数排序搞到O(n)
//coder: davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define X first
#define Y second
using namespace std;
#define LL long long
inline int read(){
int ret=0,f=1; char ch;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
if (ch=='-') f=-f;
for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-48;
return ret*f;
}
const int N = 200010;
pair<int,int>a[N];
int b[N],n,m;
int main()
{
n=read(); m=read(); n++;
for (int i=1;i<=n;i++) b[i]=read(),a[i]=make_pair(b[i],i);
sort(a+1,a+n+1);
for (int now=a[a[1].Y].Y;b[now];now=a[now].Y){
printf("%d ",b[now]);
}
}
//coder: davidwang
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define X first
#define Y second
using namespace std;
#define LL long long
inline int read(){
int ret=0,f=1; char ch;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
if (ch=='-') f=-f;
for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-48;
return ret*f;
}
const int N = 200010;
int n,m,a[N],cnt[N],next[N],now;
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();
m=read();
for (int i=1;i<=n+1;i++){
a[i]=read(); cnt[a[i]]++;
if (a[i]==0) now=i;
}
for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for (int i=m;i;i--) cnt[i]=cnt[i-1]; cnt[0]=0;
for (int i=1;i<=n+1;i++) next[++cnt[a[i]]]=i;
int i=1;
for (now=next[now],i=1;i<=n;i++,now=next[now])
printf("%d ",a[now]);
puts("");
return 0;
}
发现刚才头文件比代码要长好多不科学，然后就缩减了一下……当时这么简单的题目都没能做出来.......
