题目大意:

两列数,可以交换每列中相邻的两个数,算作一次交换

求最小的交换次数使两列数相对应的数之差的平方之和最小

思路:

首先可以明确当两列数的排序位置相对应时,为最佳答案

然后我们按照一中排序后在二中排序后出现的位置建一个数组

求一下逆序对

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#define ll long long
#define inf 2147383611
#define MAXN 100100
#define MOD 99999997
using namespace std;
inline int read()
{
int x=,f=;
char ch;ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
return x*f;
}
struct data
{
int pos,val;
bool operator < (const data &a) const
{
return val<a.val;
}
}a[MAXN],b[MAXN];
int g1[MAXN],g2[MAXN],k[MAXN],n,c[MAXN],cnt,ans;
int lowbit(int x) {return x&(-x);}
void add(int x,int val) {for(int i=x;i<=MAXN;i+=lowbit(i)) c[i]+=val;}
int sum(int x) {int res=;for(int i=x;i;i-=lowbit(i)) res+=c[i];return res;}
int main()
{
n=read();
for(int i=;i<=n;i++) a[i].val=read(),a[i].pos=i;
sort(a+,a+n+);
for(int i=;i<=n;i++) b[i].val=read(),b[i].pos=i;
sort(b+,b+n+);
for(int i=;i<=n;i++) k[a[i].pos]=b[i].pos;
for(int i=;i<=n;i++)
{
ans=((ans+i-)%MOD-sum(k[i]-)%MOD)%MOD;
add(k[i],);
}
printf("%d",ans);
}

最新文章

  1. Flash跨域传输数据 crossdomain.xml
  2. CentOS安装JDK和安装Glassfish
  3. 一步一步hadoop安装
  4. 作业4.5-2用for循环打印菱形
  5. JS---------IIFE(Imdiately Invoked Function Expression 立即执行的函数表达式)
  6. 【EF学习笔记05】----------操作内存中的数据
  7. Android之View.onMeasure方法
  8. 2013 ACM/ICPC 长沙现场赛 C题 - Collision (ZOJ 3728)
  9. Java was started but returned exit code=13
  10. hdu1540之线段树单点更新+区间合并
  11. 常用批处理命令总结3之Find和FindStr
  12. JSP中动态include和静态include区别
  13. Error:Cannot run program &quot;svn&quot; (in directory &quot;E:demo\Hello&quot;): CreateProcess error=2,
  14. Chrom Firefox 非安全端口访问
  15. 浅谈运维中的安全问题-FTP篇
  16. Cas 服务器 使用HTTP协议对外服务
  17. 转://Oracle中定义者权限和调用者权限案例分析
  18. LeetCode(80):删除排序数组中的重复项 II
  19. httpstatus类的状态有哪些
  20. PXE(preboot execution environment):【网络】预启动执行环节:引导 live光盘 ubuntu livecd 18.04+:成功

热门文章

  1. Linux命令整理(2018/9/9-2018/9/15)
  2. Python之面向对象slots与迭代器协议
  3. Spider-scrapy 中的 xpath 语法与调试
  4. Python关于函数作为返回值的理解(3分钟就看完了)
  5. 商业研究(21):活力蛙,足疗O2O,曾经的“中国上门足疗领先品牌”
  6. .DS_Store的说明
  7. 命令行下设置 PYTHONPATH 来正确运行Python代码
  8. poj3440--Coin Toss(几何上的概率)
  9. [NOIP2005] 普及组 循环
  10. 【ZJOI2018 Round2游记】