HDU 5775 Bubble Sort [树状数组]【数据结构】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5775 ———————————————————-. Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Problem Description for(int i=1;i<=N;++i) After the sort,the array is in increasing order. ?? wants to know the absolute values of difference of rightmost place and leftmost place for every number it reached. Input limits Output Sample Input Sample Output Hint Author Source ———————————————————–. 题目大意: 解题思路: 然后用树状数组维护两遍就行了 附本题代码 #include <bits/stdc++.h>
#define abs(x) (((x)>0)?(x):-(x))
#define lalal puts("*********")
#define Rep(a,b,c) for(int a=(b);a<=(c);a++)
#define Req(a,c) for(int a=(b);a>=(c);a--)
#define Rop(a,c) for(int a=(b);a<(c);a++)
#define s1(a) scanf("%d",&a)
using namespace std;
/**************************************/
const int N = 100000+5;
#define lowbit(x) (x&-x)
int sum[N],cnt,ans[N],a[N];
void update(int index,int val){
for(int i=index;i<=cnt;i+=lowbit(i))
sum[i]+=val;
return;
}
int getSum(int index){
int ans = 0;
for(int i=index;i>0;i-=lowbit(i))
ans+=sum[i];
return ans;
}
int main(){
int _,kc,x;
while(~s1(_)){
kc=0;
while(_--){
s1(cnt);
memset(sum,0,sizeof(sum));
memset(ans,sizeof(ans));
Rep(i,1,cnt){
s1(a[i]);
ans[a[i]] =getSum(cnt)-getSum(a[i]);
update(a[i],1);
}
memset(sum,sizeof(sum));
Req(i,1){
ans[a[i]] =max(ans[a[i]],getSum(a[i]));
update(a[i],1);
}
printf("Case #%d:",++kc);
Rep(i,cnt) printf(" %d",ans[i]);
puts("");
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |