luogu 1966 火柴排队
2024-08-29 01:35:18
题目大意:
两列数,可以交换每列中相邻的两个数,算作一次交换
求最小的交换次数使两列数相对应的数之差的平方之和最小
思路:
首先可以明确当两列数的排序位置相对应时,为最佳答案
然后我们按照一中排序后在二中排序后出现的位置建一个数组
求一下逆序对
#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);
}
最新文章
- Flash跨域传输数据 crossdomain.xml
- CentOS安装JDK和安装Glassfish
- 一步一步hadoop安装
- 作业4.5-2用for循环打印菱形
- JS---------IIFE(Imdiately Invoked Function Expression 立即执行的函数表达式)
- 【EF学习笔记05】----------操作内存中的数据
- Android之View.onMeasure方法
- 2013 ACM/ICPC 长沙现场赛 C题 - Collision (ZOJ 3728)
- Java was started but returned exit code=13
- hdu1540之线段树单点更新+区间合并
- 常用批处理命令总结3之Find和FindStr
- JSP中动态include和静态include区别
- Error:Cannot run program ";svn"; (in directory ";E:demo\Hello";): CreateProcess error=2,
- Chrom Firefox 非安全端口访问
- 浅谈运维中的安全问题-FTP篇
- Cas 服务器 使用HTTP协议对外服务
- 转://Oracle中定义者权限和调用者权限案例分析
- LeetCode(80):删除排序数组中的重复项 II
- httpstatus类的状态有哪些
- PXE(preboot execution environment):【网络】预启动执行环节:引导 live光盘 ubuntu livecd 18.04+:成功
热门文章
- Linux命令整理(2018/9/9-2018/9/15)
- Python之面向对象slots与迭代器协议
- Spider-scrapy 中的 xpath 语法与调试
- Python关于函数作为返回值的理解(3分钟就看完了)
- 商业研究(21):活力蛙,足疗O2O,曾经的“中国上门足疗领先品牌”
- .DS_Store的说明
- 命令行下设置 PYTHONPATH 来正确运行Python代码
- poj3440--Coin Toss(几何上的概率)
- [NOIP2005] 普及组 循环
- 【ZJOI2018 Round2游记】