本文主要是介绍hdu1394(线段树点更新的应用)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：求一个序列经过一定的操作得到的序列的最小逆序数
这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1)
知道上面的知识点后，可以用暴力来解
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 50005
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N],num[N];
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int n;while(scanf("%d",&n) != EOF){int i, j;for(i = 0; i < n; i++)scanf("%d",&a[i]);memset(num,0,sizeof(num));int res = 0;for(i = 1; i < n; i++){for(j = 0; j < i; j++)if(a[i] < a[j])num[i]++;res += num[i];}int minn = res;for(i = 0; i < n-1; i++){res = res-a[i]+n-1-a[i];//cout<<res<<endl;if(res < minn) minn = res;}printf("%d\n",minn);}return 0;
}
思路入下：
这里的线段树只用来求逆序数，依次输入一个数据a，a所在的区间都加1，然后查询[ a , n ]上的sum，这就是a的逆序数
为了方便理解，最好自己举个例子
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 50005
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int a[N],c[N];
struct node
{int l,r,sum;
}tree[N*4];
int res;
void build(int o,int l,int r)
{tree[o].l = l;tree[o].r = r;if(l == r){tree[o].sum = 0;return ;}int m = (l + r)/2;build(2*o,l,m);build(2*o+1,m+1,r);tree[o].sum = tree[2*o].sum + tree[2*o+1].sum;
}
void insert(int o,int k)
{if(tree[o].l == tree[o].r){tree[o].sum = 1;return;}int m = (tree[o].l+tree[o].r)/2;if(k <= m) insert(2*o,k);if(k > m) insert(2*o+1,k);tree[o].sum = tree[2*o].sum + tree[2*o+1].sum;
}
void query(int o,int x,int y)
{if(x <= tree[o].l && tree[o].r <= y){res += tree[o].sum;return;}int m = (tree[o].l + tree[o].r)/2;if(x <= m)query(2*o,x,y);if(y > m)query(2*o+1,x,y);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int n;while(scanf("%d",&n) != EOF){int i,ans = 0;build(1,1,n);for(i = 0; i < n; i++){scanf("%d",&a[i]);insert(1,a[i]+1);res = 0;query(1,a[i]+2,n);c[i] = res;ans += c[i];}int minn = ans;//cout<<ans<<endl;for(i = 0; i < n-1; i++)//把n-1个数字依此移到最后{ans = ans - a[i] + (n-a[i]-1);//每个数依此移到最后得到的逆序数// cout<<ans<<endl;if(minn > ans)minn = ans;}printf("%d\n",minn);}return 0;
}
这篇关于hdu1394(线段树点更新的应用)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
