点击打开链接hdu2689
思路:线段树+单点更新
分析:
1 题目给定n个数要求最少的交换次数使得序列有序
2 显然两个数要交换肯定是满足i < j && num[i] > num[j]。那么假设现在读入一个数num[i],我们要求这个数num[i]要和前面的交换几次使得序列有序,就是查找num[0]~num[i-1]之间比num[i]大的数的个数,那么这个过程我们就可以利用线段树的查找,我们只要去查找[num[i]+1 , n]这个区间已经插入的个数即可,然后更新线段树
3 注意当num[i] == n的时候不用查找,直接更新
4 题目给定n 最大为1000,那么最话的情况下次数是1+2+3+...n,那么不会超过int。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
int n;
struct Node{
int left;
int right;
int num;
};
Node node[4*MAXN];
//建立一颗空的线段树
void buildTree(int left , int right , int pos){
node[pos].left = left;
node[pos].right = right;
node[pos].num = 0;
if(left == right)
return;
int mid = (left+right)>>1;
buildTree(left , mid , pos<<1);
buildTree(mid+1 , right , (pos<<1)+1);
node[pos].num = node[pos<<1].num + node[(pos<<1)+1].num;
}
//询问
int query(int left , int right , int pos){
if(node[pos].left == left && node[pos].right == right)
return node[pos].num;
int mid = (node[pos].left + node[pos].right)>>1;
if(right <= mid)
return query(left , right , pos<<1);
else if(left > mid)
return query(left , right , (pos<<1)+1);
else
return query(left , mid , pos<<1)+query(mid+1 , right , (pos<<1)+1);
}
//更新
void update(int index , int pos){
if(node[pos].left == node[pos].right){
node[pos].num++;
return;
}
int mid = (node[pos].left + node[pos].right)>>1;
if(index <= mid)
update(index , pos<<1);
else
update(index , (pos<<1)+1);
node[pos].num = node[pos<<1].num+node[(pos<<1)+1].num;
}
int main(){
int x , ans;
while(scanf("%d" , &n) != EOF){
buildTree(1 , n , 1);
ans = 0;
for(int i = 1 ; i <= n ; i++){
scanf("%d" , &x);
if(x != n)
ans += query(x+1 , n , 1);
update(x , 1);
}
printf("%d\n" , ans);
}
return 0;
}
思路:树状数组
分析:
1 题目给定n个数要求最少的交换次数使得序列有序序列
2 显然两个数要交换肯定是满足i < j && num[i] > num[j]。那么假设现在读入一个数num[i],我们要求这个数num[i]要和前面的交换几次使得序列有序,就是查找num[0]~num[i-1]之间比num[i]大的数的个数。那么如果我们用树状数组来做的话,读入num[i]的时候我们应该查找前i-1个数比num[i]大的数,那么个数就是i-1-getSum(x-1),当x为1的时候就是i-1。最后更新树状数组。(这里原数组A[I]表示的是i是否插入,A[i]的值只有0/1两种!)
3 题目给定n 最大为1000,那么最话的情况下次数是1+2+3+...n,那么不会超过int。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1010
int num[MAXN];
int C[MAXN];
int lowbit(int x){
return x&(-x);
}
int getSum(int x){
int sum = 0;
while(x > 0){
sum += C[x];
x -= lowbit(x);
}
return sum;
}
void update(int x){
while(x <= MAXN){
C[x] += 1;
x += lowbit(x);
}
}
int main(){
int x , ans , n;
while(scanf("%d" , &n) != EOF){
memset(num , 0 , sizeof(num));
memset(C , 0 , sizeof(C));
ans = 0;
for(int i = 1 ; i <= n ; i++){
scanf("%d" , &x);
if(x > 1)
ans += i-1-getSum(x-1);
else
ans += i-1;
update(x);//更新树状数组
}
printf("%d\n" , ans);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
Hdu 1237 解题代码