sgu 180. Inversions (树状数组+离散化,第一道需要改模板的题目,好题)

本文主要是介绍sgu 180. Inversions (树状数组+离散化,第一道需要改模板的题目,好题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、http://blog.csdn.net/sdjzping/article/details/20381665

2、题目大意:

有n个数字,定义i<j并且a[i]>a[j]这样的一对数为逆序对,求这个数中有多少逆序对,

3、题目分析

看着题目很简单,但是n=65537,两重for循环找必超时,所以想到了用树状数组,但是交了好几遍都错了,runtime error,原因就是数组中的数字可以到达10^9,数组肯定要超内存,此题需要用到离散化,但是数字之间可能有重复,这一点没考虑到,有wrong 了好几遍,不过终于是改对了,。

4、题目:

180. Inversions
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard




 

There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=i<j<=N and A[i]>A[j].

Input
The first line of the input contains the number N. The second line contains N numbers A1...AN.

Output
Write amount of such pairs.

Sample test(s)

Input

 

 
5 2 3 1 5 4
 

Output

 

 
3
 

5、AC代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 65540
#define ll long long
int n;
int c[N];
struct node
{int id;int v;
}a[N];
node b[N];
int cmp(node a,node b)
{return a.v<b.v;
}
int cmp1(node a,node b)
{return a.id<b.id;
}int lowbit(int i)
{return i&(-i);
}
void update(int x,int v)
{for(int i=x;i<=n;i+=lowbit(i)){c[i]+=v;}
}
ll getsum(int x)
{ll sum=0;//此处注意需要计算的是比自己小的,所以不包含自己for(int i=x-1;i>=1;i-=lowbit(i)){sum+=c[i];}return sum;
}
int main()
{while(scanf("%d",&n)!=EOF){memset(c,0,sizeof(c));for(int i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].id=i;}sort(a+1,a+n+1,cmp);a[0].v=-1;int k=1;//注意离散化的时候考虑相等的情况for(int i=1;i<=n;i++){if(a[i].v!=a[i-1].v){b[i].id=a[i].id;b[i].v=k++;}else{b[i].id=a[i].id;b[i].v=b[i-1].v;}}sort(b+1,b+n+1,cmp1);ll sum=0;for(int i=n;i>=1;i--){sum+=getsum(b[i].v);update(b[i].v,1);}printf("%lld\n",sum);}return 0;
}


 

这篇关于sgu 180. Inversions (树状数组+离散化,第一道需要改模板的题目,好题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/369640

相关文章

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <