首页 > Gym - 102082G

Gym - 102082G

Gym - 102082G

https://vjudge.net/problem/2198225/origin

对于数列中任意一个数，要么从最左边到它不递减，要么从最右边到到它不递减，为了满足这个条件，就要移动，而移动的最少步数就是逆序对数。所以这个数要么往左移动，要么往右移动，所以两个取最小就好了

#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#include
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 1000010
#define For(i,a,b) for(long long i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()using namespace std;
long long n,len,ans,k;
long long a[N],b[N],c[N],temp,d1[N],d2[N];
long long t[N];
void in(long long &x){long long y=1;char c=g();x=0;while(c<'0'||c>'9'){if(c=='-')y=-1;c=g();}while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=g();}x*=y;
}
void o(long long x){if(x<0){p('-');x=-x;}if(x>9)o(x/10);p(x%10+'0');
}void modify(long long k){for(;k<=n;k+=k&(-k))t[k]++;
}long long getnum(long long k){long long cnt=0;for(;k>0;k-=k&(-k))cnt+=t[k];return cnt;
}int main(){in(n);For(i,1,n){in(a[i]);b[i]=a[i];c[i]=a[i];}sort(b+1,b+n+1);sort(c+1,c+n+1);len=unique(b+1,b+n+1)-b-1;For(i,1,n)a[i]=lower_bound(b+1,b+n+1,a[i])-b;For(i,1,n){modify(a[i]);d1[i]=i-getnum(a[i]);}memset(t,0,sizeof(t));for(long long i=n;i;i--){modify(a[i]);d2[i]=n-i-getnum(a[i])+1;}For(i,1,n)ans+=min(d1[i],d2[i]);o(ans);return 0;
}

 

转载于:https://www.cnblogs.com/war1111/p/11199791.html

更多相关：

  • 雪花算法 Java 版

    雪花算法根据时间戳生成有序的 64 bit 的 Long 类型的唯一 ID 各 bit 含义： 1 bit: 符号位，0 是正数 1 是负数， ID 为正数，所以恒取 041 bit: 时间差，我们可以选择一个参考点，用它来计算与当前时间的时间差 (毫秒数)，41 bit 存储时间差，足够使用 69 年10 bit: 机器码，能编...

  • dp专题练习

      这是一篇很水的blog 扫雷 link 一道很水的dp，考虑上一上，这一行，与下一行是否有雷即可 #include #include #include #include using namespace std; inline long long read...

  • Codeforces 900D Unusual Sequences：记忆化搜索

    题目链接：http://codeforces.com/problemset/problem/900/D 题意： 　　给定x,y，问你有多少个数列a满足gcd(a[i]) = x 且 ∑(a[i]) = y。   题解： 　　由于gcd(a[i]) = x，所以y一定是x的倍数，否则无解。 　　那么原题就等价于：问你有多少个数列a满足g...

  • 洛谷P2429 制杖题 [2017年6月计划 数论10]

    P2429 制杖题 题目描述 求不大于 m 的、 质因数集与给定质数集有交集的自然数之和。 输入输出格式 输入格式：第一行二个整数 n，m。 第二行 n 个整数，表示质数集内的元素 p[i]。 输出格式：一个整数，表示答案，对 376544743 取模。 输入输出样例 输入样例#1：2 15 3 5 输出样例#1：60 说...

  • PCL点云分割（2）

    关于点云的分割算是我想做的机械臂抓取中十分重要的俄一部分，所以首先学习如果使用点云库处理我用kinect获取的点云的数据，本例程也是我自己慢慢修改程序并结合官方API 的解说实现的，其中有很多细节如果直接更改源程序，可能会因为数据类型，或者头文件等各种原因编译不过，会导致我们比较难得找出其中的错误，首先我们看一下我自己设定的一个场景，...

  • PCL点云配准（2）

    /* 使用正态分布变换进行配准的实验 。其中room_scan1.pcd room_scan2.pcd这些点云包含同一房间360不同视角的扫描数据 */ #include #include #include #include

  • PCL点云变换与移除NaN

    #include #include #include #include ...

  • PCL滤波介绍(3)

    #include #include #include #include #include #include...

  • PCL滤波介绍（2）

    #include #include #include #include int main (int argc,...

  • 引用-ZIGBEE-ZSTACK网络配置相关问题

    下面是以道友问的问题，这里简单做分析，仅供交流学习用，有什么不对之处还请各位大虾指正。鄙人邮箱为：[email protected]. 欢迎交流！！1： 最主要的就是路由问题。我用06协议栈自带的例子程序sampleapp修改了一下，另协调器以网络地址的形式向终端发送数据，中间加入路由转发数据。拿 到室外试验了一下，结果路由根本不起...

  • [HDOJ2819]Swap（二分图最大匹配, 匈牙利算法）

    题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=2819 题意：给一张n*n的01矩阵，可以任意交换其中的行或者列，问是否可以交换出来一个对角线上都是1的矩阵。 按行列号建图，如果(i,j)为1的话，则i和j就有一条边。匹配出的结果可以认为如何交换使得行列相等，输出结果要注意不...

  • BootLoader引导程序制作及移植(一)

    U-Boot 实验指导书 一、获得U-Boot 源码 我们的光盘中提供了直接从U-Boot的官方网站下载的源代码，版本是1.3.2，放在src目录下。将u-boot-1.3.2.tar.bz2拷贝了工作目录下，解压源码包： [root@localhost root]# mkdir 2410-s [root@localhost roo...

  • 基于OHCI的USB主机 —— USB设备常量定义

    USB设备枚举过程中使用到的常量定义如下： /*-------------------------------------------------------------------------  * Standard Chapter 9 definition  *----------------------------------...

©2024 11GX.COM