P1966 火柴排队(逆序对)
2024-08-30 03:47:53
P1966 火柴排队
题目描述
涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为: ∑(ai-bi)^2
其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。
输入输出格式
输入格式:
输入文件为 match.in。
共三行,第一行包含一个整数 n,表示每盒中火柴的数目。
第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。
第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。
输出格式:
输出文件为 match.out。
输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。
输入输出样例
输入样例#1:
【输入输出样例 1】
4
2 3 1 4
3 2 1 4
【输入输出样例 2】
4
1 3 4 2
1 7 2 4
输出样例#1:
【输入输出样例 1】
1
【输入输出样例 2】
2
说明
【输入输出样例说明1】
最小距离是 0,最少需要交换 1 次,比如:交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。
【输入输出样例说明2】
最小距离是 10,最少需要交换 2 次,比如:交换第 1 列的中间 2 根火柴的位置,再交换第 2 列中后 2 根火柴的位置。
【数据范围】
对于 10%的数据, 1 ≤ n ≤ 10;
对于 30%的数据,1 ≤ n ≤ 100;
对于 60%的数据,1 ≤ n ≤ 1,000;
对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤火柴高度≤ maxlongint
/*
公式化简后要求Σai*bi的最小值
根据均值不等式plus plus+直观感受
aibi越接近乘积就越大
所以考虑a b 一一对应
离散化后
先把a排序并记录b对应a的位置
然后处理b。因为a是有序的b也成为有序的求最小交换次数
那就是求b的逆序个数咯
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> #define ll long long
#define N 100007
#define mod 99999997
#define inf 2147483647 using namespace std;
ll n,m,ans,tot;
ll s[N];
struct ta
{
ll val,id;
bool operator < (const ta &a)const{
return val<a.val;
}
};
ta a[N],b[N];
struct tree
{
ll l,r,sum;
}tr[N<<]; inline ll read()
{
ll x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void pushup(ll k)
{
tr[k].sum=tr[k<<].sum+tr[k<<|].sum;
} void build(ll k,ll l,ll r)
{
tr[k].l=l;tr[k].r=r;
if(l==r)
{
tr[k].sum=;
return;
}
ll mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
} void insert(ll k,ll pos)
{
if(tr[k].l==tr[k].r && tr[k].l==pos)
{
tr[k].sum=(tr[k].sum+)%mod;
return;
}
ll mid=(tr[k].l+tr[k].r)>>;
if(pos<=mid) insert(k<<,pos);
if(pos>mid) insert(k<<|,pos);
pushup(k);
} ll query(ll k,ll l,ll r)
{
if(l>r) return ;
if(tr[k].l==l && tr[k].r==r)
return tr[k].sum;
ll mid=(tr[k].l+tr[k].r)>>;
if(r<=mid) return query(k<<,l,r)%mod;
else if(l>mid) return query(k<<|,l,r)%mod;
else return query(k<<,l,mid)%mod+query(k<<|,mid+,r)%mod;
} void love()
{
build(,,tot);ans=;
for(int i=;i<=n;i++)
{
insert(,s[i]);
ans+=query(,s[i]+,tot)%mod;
ans%=mod;
}
} int main()
{
n=read();tot=;
for (int i=;i<=n;i++){a[i].val=read();a[i].id=i;}
for (int i=;i<=n;i++){b[i].val=read();b[i].id=i;tot=max(tot,b[i].val);}
sort(a+,a+n+);
sort(b+,b+n+);
for (int i=;i<=n;i++) s[a[i].id]=b[i].id;
love();
printf("%lld\n",ans);
return ;
}
最新文章
- C语言文法
- C++多线程编程(入门实例)
- Linux将Shelll输出写入到文件
- Django--models表操作
- An Example of Pre-Query and Post-Query Triggers in Oracle Forms With Using Display_Item to Highlight Dynamically
- VBA添加表格
- 正确理解SQL Server的许可证(转)
- iOS10-配置获取隐私数据权限声明
- Foundation 学习笔记
- csdn的调查问卷,好多都不懂哈
- 设置input框文字垂直居中和宽度
- javascript如何自动去除所有空格?
- 面向对象进阶---attr家族
- sqlmap基础入门超详细教程
- numpy通用函数
- IO流巧记图
- 面试加分项---HashMap底层实现原理
- 关于Web中列表页面的加载问题
- WEB入门之十二 jquery简介
- UITableView加载网络数据的优化