poj1703 Lost Cows

给定集合{1,2,...,n}的一个置换,指定每个位置上在其左方且比其小的数的个数,求该置换。

这题我目前还只会O(n^2)的做法。

以后再用更高效的算法解决。

http://poj.org/problem?id=2182

 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 8e3 + ;
int n;
struct Point{
int id, idx;
}a[maxn]; bool cmp(Point x, Point y) { return x.idx < y.idx; } int main(){
freopen("in.txt", "r", stdin);
while(~scanf("%d", &n)){
for(int i = ; i <= n; i++) a[i].id = i;
a[].idx = ;
for(int i = , t; i <= n; i++){
scanf("%d", &t);
if(t + == i) a[i].idx = i;
else{
for(int j = i; j > t + ; j--) a[j].idx = a[j - ].idx;
a[t + ].idx = i;
}
}
sort(a + , a + n + , cmp);
for(int i = ; i <= n; i++) printf("%d\n", a[i].id);
}
return ;
}
上一篇:kazoo python zookeeper 选主


下一篇:[have_fun] 好玩哒小游戏又来啦