树状数组
题目：
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高. 现在这n头奶牛站成一列，已知第i头牛前面有Ai头牛比它低，求每头奶牛的身高.
解题思路：
首先记录一个01序列，起初都为1，从n到1倒着操作，每次查找第Ai + 1小的数即可，然后把那个数后面那个数标记成0 . 前缀和用树状数组维护,查找用二分
二分 + 树状数组
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
| #include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int n;
int a[N], b[N];
int c[N];
void add(int x, int y){
while(x < N){
c[x] += y;
x += x & -x;
}
}
ll ask(int x){
ll ans = 0;
while(x){
ans += c[x];
x -= x & -x;
}
return ans;
}
int main()
{
scanf("%d", &n);
for(int i = 2; i <= n; i++){
scanf("%d", &a[i]);
}
for(int i = 2; i <= n; i++){
add(i, 1);
}
for(int i = n; i; i--){
int l = 1, r = n, ans;
while(l <= r){
int mid = (l + r) / 2;
if(ask(mid) >= a[i]){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
b[i] = ans;
add(ans, -1);
}
for(int i = 1; i <= n; i++){
printf("%d\n", b[i]);
}
return 0;
}
|
题目：
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高. 现在这n头奶牛站成一列，已知第i头牛前面比它低的牛身高总和为Ai，求每头奶牛的身高.
解题思路：
首先记录一个序列，起初为1, 2, 3…n，从n到1倒着操作，每次查找前缀和为Ai数即可，然后把那个数后面那个数标记成0 .
二分 + 树状数组
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
| #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int b[N], n;
ll c[N], a[N];
void add(int x, int y){
while(x < N){
c[x] += y;
x += x & -x;
}
}
ll query(int x){
ll ans = 0;
while(x){
ans += c[x];
x -= x & -x;
}
return ans;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
add(i, i);
}
for(int i = n; i; i--){
int l = 1, r = n, mid, ans;
while(l <= r){
mid = (l + r) >> 1;
if(query(mid) > a[i]){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
b[i] = ans;
add(ans, -ans);
}
for(int i = 1; i <= n; i++){
printf("%d ", b[i]);
}
return 0;
}
|
