这一个月，算上四场13年的现场上做了大约15场左右。周日，今年的最后一场
TheLastStand的一题，题意是基于堆排序的构造题，倒着推每个点就行，以次得到val值为n-1的id
#include #include #include #include #include #include #include #include #include #include #define REP(i, n) for(int i=0; i<(n); i++) #define CLR(a, b) memset(a, b, sizeof(a)) #define LL long long using namespace std; const int maxn = 51000; int id[maxn]; int val[maxn]; int n; int now; void get(int x) { int idx = id[1]; vector v; v.push_back(x); while (x != 1) x /= 2,v.push_back(x); int sz = v.size(); for (int i = sz - 1; i > 0; i--) id[v[i]] = id[v[i - 1]]; val[id[1]] = now; id[now] = idx; swap(id[1], id[now]); } int main() { while (~scanf("%d", &n)) { REP(i, n + 1) id[i] = i; val[1] = n; swap(id[1], id[n]); now = n - 1; for (int i = n - 1; i >= 1; i--, now--) get(i); for (int i = 1; i <= n; i++) printf("%d%c", val[i], i == n '\n' : ' '); } }
UVALive 3222 Joke with Turtles