Lost Cows
N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.
Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.
Given this data, tell FJ the exact ordering of the cows.
Input
* Line 1: A single integer, N
* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.
Output
* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.
Sample Input
5
1
2
1
0
Sample Output
2
4
5
3
1
Source
题目类型：动态第k大查询
算法分析：从后向前确定每个数，可知当前数(输入值为k)是还未确定数中的第k + 1大的数，则可以维护一个线段树来动态查找
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
/************************************************* Author :supermaker Created Time :2015/12/15 23:38:23 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r int aa[maxn], out[maxn], sum[maxn<<2], n; void PushUp (int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void Build (int rt, int l, int r) { if (l == r) { sum[rt] = 1; return ; } int m = (l + r) >> 1; Build (lson); Build (rson); PushUp (rt); } int Query (int rt, int l, int r, int val) { if (l == r) return l; int m = (l + r) >> 1; if (val <= sum[rt<<1]) return Query (lson, val); else return Query (rson, val - sum[rt<<1]); } void UpDate (int rt, int l, int r, int val) { if (l == r) { sum[rt] = 0; return ; } int m = (l + r) >> 1; if (val <= m) UpDate (lson, val); else UpDate (rson, val); PushUp (rt); } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { for (int i = 2; i <= n; i++) scanf ("%d", &aa[i]); aa[1] = 0; Build (1, 1, n); for (int i = n; i >= 1; i--) { int tt = Query (1, 1, n, aa[i] + 1); out[i] = tt; UpDate (1, 1, n, tt); } for (int i = 1; i <= n; i++) printf ("%d\n", out[i]); } return 0; } |