当前位置: 代码迷 >> 综合 >> 北京化工大学2018年10月程序设计竞赛 问题 D: 积木 树状数组
  详细解决方案

北京化工大学2018年10月程序设计竞赛 问题 D: 积木 树状数组

热度:65   发布时间:2024-01-15 07:22:40.0

问题 D: 积木

时间限制: 1 Sec  内存限制: 128 MB
提交: 503  解决: 49
[提交] [状态] [讨论版] [命题人:admin]

 

题目描述

我懒得编故事了  m哥牛逼!
有n个积木,第i个积木的高度为a[i],求每个积木前面有几个比它矮的积木

 

输入

多组输入,每组由两行组成,第一行输入n,第二行输入n个数,为n个积木的高度a[i]
//(1<=n<=100000)(1<=a[i]<=1000000000)

 

输出

每组数据输出n个数,第i个数为第i个积木前面比他矮的积木的个数

 

样例输入

5
1 2 3 4 5

 

样例输出

0 1 2 3 4

 

比赛时尝试了很多种做法都是超时,不过也没事,是自己没学过的东西树状数组,看这题之前应该先看这一个题,

UVA1428 Ping pong(树状数组+思维)

这题给这个题提供了做法,但是按照那一个题还不能做,因为a[i]的数值过大,10e9,数组下拨肯定不行,但下面的解决方法很妙,就是你把所有的数保存到另一个数组中去,排序,去重,这个数组的值域就是a[i]的范围,精华来了,他们对应的下标就可以代表每一个值,所以,对下标位置进行标记。

#include<stdio.h>
#include<string>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;const int MAXN=100000+5;//最大元素个数int n;//元素个数
int l[MAXN],b[MAXN],a[MAXN],c[MAXN];//返回i的二进制最右边1的值
int lowbit(int i)
{return i&(-i);
}//返回A[1]+...A[i]的和
int sum(int i)
{int res=0;while(i>0){res += c[i];i -= lowbit(i);}return res;
}//令A[i] += val
void add(int i,int val)
{while(i<=n){c[i] += val;i += lowbit(i);}
}
int main()
{while(scanf("%d",&n)!=EOF){   memset(l,0,sizeof(l));for(int i=1;i<=n;i++)  {scanf("%d",&a[i]); b[i]=a[i];  } sort(b+1,b+n+1); unique(b+1,b+n+1); //去重memset(c,0,sizeof(c));for(int i=1;i<=n;i++){int pos=lower_bound(b+1,b+n+1,a[i])-b;l[i]=sum(pos);add(pos+1,1);printf("%d%c",l[i],i==n?'\n':' ');}}return 0;
}

 

  相关解决方案