文章
26
粉丝
407
获赞
0
访问
335.4k
有n头奶牛,已知它们的身高为 1~n 且各不相同,但不知道每头奶牛的具体身高。
现在这nn头奶牛站成一列,已知第i头牛前面有AiAi头牛比它低,求每头奶牛的身高。
输入格式
第1行:输入整数nn。
第2..n行:每行输入一个整数AiAi,第i行表示第i头牛前面有AiAi头牛比它低。
(注意:因为第1头牛前面没有牛,所以并没有将它列出)
输出格式
输出包含nn行,每行输出一个整数表示牛的身高。
第ii行输出第ii头牛的身高。
二分:
int search(int l,int r){
while (l < r){
int mid = l + r >> 1;
if (check(mid) < a[i] + 1){
l = mid + 1;
}
else{
r = mid;
}
}
return l;
}
#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int n;
int c[N], a[N], ans[N];//ans[N]记录牛的高度
int lowbit(int x){
return x&(-x);
}
void add(int x, int y){
for (int i = x; i <= n; i += lowbit(i)){
c[i] += y;
}
}
int ask(int x){
int res = 0;
for (int i = x; i; i -= lowbit(i)){
res += c[i];
}
return res;
}
int main(){
cin >> n;
add(1, 1);
for (int i = 2; i <= n; i++){
cin >> a[i];
add(i, 1);
}
for (int i = n; i >= 1; i--){
int l = 1, r = n;
while (l < r){
int mi...
登录后发布评论
暂无评论,来抢沙发