问题 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;
}