HDU 2838 Cow Sorting [树状数组]【数据结构】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2838 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description Please help Sherlock calculate the minimal time required to reorder the cows. Input Output Sample Input Sample Output Hint Input Details Three cows are standing in line with respective grumpiness levels 2,3,and 1. 2 3 1 : Initial order. Source —————————————————-. 题目大意: 解题思路: 这里直接采取了维护两个树状数组的暴力思路: 注意要用I64 否则溢出了… 附本题代码 #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)
typedef long long int LL;
using namespace std;
/**************************************/
const int N = 100000+5;
#define lowbit(x) (x&-x)
LL sum1[N],sum2[N];
int cnt;
void update1(int index,int val){
for(int i=index;i<=cnt;i+=lowbit(i))
sum1[i]+=val;
return ;
}
LL getSum1(int index){
LL ans=0;
for(int i=index;i>0;i-=lowbit(i))
ans+=sum1[i];
return ans;
}
void update2(int index,int val){
for(int i=index;i<=cnt;i+=lowbit(i))
sum2[i]+=val;
return ;
}
LL getSum2(int index){
LL ans=0;
for(int i=index;i>0;i-=lowbit(i))
ans+=sum2[i];
return ans;
}
int main(){
while(~s1(cnt)){
int x;
LL ans=0;
memset(sum1,0,sizeof(sum1));
memset(sum2,sizeof(sum2));
Rep(i,1,cnt){
s1(x);
ans+=x*(getSum2(cnt)-getSum2(x))+(getSum1(cnt)-getSum1(x));
update1(x,x);
update2(x,1);
}
printf("%I64dn",ans);
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |