考虑把一次交换产生的贡献记录在交换的两个数字中较小的那个数字上。则构造一个好的序列的过程可以看成是:按照从小到大的顺序枚举每个数,每次选择将这个数放在序列的左边或右边。
不难发现,每次放到左边或右边需要移动的次数是初始序列中左边或右边比这个数大的数的个数,与其它数选择放在左边还是右边无关。
直接用树状数组计算即可,时间复杂度 \(𝑂(𝑛 \log 𝑛)\)。
//10692 Problem D:【2022NOIP联测10 10月17日】交换(swap)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define int long long
const int MAXN=3e5+5;
int n,a[MAXN],c[MAXN];
vector<int> bin[MAXN];
#define lowbit(x) ((x)&-(x))
void add(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=k;
return;
}
int sum(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
res+=c[i];
return res;
}
signed main()
{
int m,x,y,ans=0;
scanf("%lld",&n);
m=n;
for(int i=1;i<=n;i++)
{
scanf("%lld",a+i);
add(i,1);
bin[a[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<(int)bin[i].size();j++)
{
x=sum(bin[i][j]-1);
y=m-x-1;
ans+=min(x,y-(int)bin[i].size()+j+1);
add(bin[i][j],-1);
m--;
}
}
printf("%lld\n",ans);
return 0;
}
/*
* AcCoders-2022NOIPA层联测10 10月17日
* http://www.accoders.com/problem.php?cid=4207&pid=3
* C++23 -O0
* 2022.10.17
*/
原文地址:http://www.cnblogs.com/2020gyk080/p/16800237.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性