hdu-5497 Inversion(滑动窗口+树状数组)
发布日期:2021-08-19 16:01:00 浏览次数:1 分类:技术文章

本文共 2373 字,大约阅读时间需要 7 分钟。

题目链接:

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1087    Accepted Submission(s): 323

Problem Description
You have a sequence 
{
a1,a2,...,an}
 and you can delete a contiguous subsequence of length m. So what is the minimum number of inversions after the deletion.
 

 

Input
There are multiple test cases. The first line of input contains an integer 
T, indicating the number of test cases. For each test case:
The first line contains two integers n,m(1n105,1m<n) - the length of the seuqence. The second line contains n integers a1,a2,...,an(1ain).
The sum of n in the test cases will not exceed 2×106.
 

 

Output
For each test case, output the minimum number of inversions.
 

 

Sample Input
2
3 1
1 2 3
4 2
4 1 3 2
 

 

Sample Output
0
1
 
题意:
有一个序列,然后你可以删除一个长度为mm的连续子序列. 问如何删除才能使逆序对最少. 思路: 也是套路,逆序对可以用树状数组求得,连续的可以使用滑动窗口,跟尺取法差不多啦;开了两个树状数组一个记录左边界之前的数,一个记录右边界后面的数,然后更新逆序对的数目,取最小就好了; AC代码:
#include 
using namespace std;typedef long long LL;const int maxn=1e5+10;int sum1[maxn],sum2[maxn],n,m,a[maxn];int lowbit(int x){return x&(-x);}inline void update1(int x,int num){ while(x<=n) { sum1[x]+=num; x+=lowbit(x); }}inline int query1(int x){ int s=0; while(x) { s+=sum1[x]; x-=lowbit(x); } return s;}inline void update2(int x,int num){ while(x<=n) { sum2[x]+=num; x+=lowbit(x); }} inline int query2(int x){ int s=0; while(x) { s+=sum2[x]; x-=lowbit(x); } return s;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++)sum1[i]=sum2[i]=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]); LL su=0; for(int i=n;i>0;i--) { su=su+query2(a[i]-1); update2(a[i],1); } LL ans=su,temp=su;int l,r=1; for(l=1;l<=n-m+1;l++) { while(r-l
<=n) { update2(a[r],-1); temp=temp-query2(a[r]-1); temp=temp-(l-1-query1(a[r])); r++; } ans=min(ans,temp); temp=temp+(l-1-query1(a[l])); temp=temp+query2(a[l]-1); update1(a[l],1); } printf("%lld\n",ans); } return 0;}

  

 

转载于:https://www.cnblogs.com/zhangchengc919/p/5922283.html

转载地址:https://blog.csdn.net/weixin_30940783/article/details/97957015 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Powershell实现创建zip压缩文件
下一篇:hdu-5695 Gym Class(贪心+拓扑排序)

发表评论

最新留言

不错!
[***.144.177.141]2024年03月10日 00时54分41秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍 2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解 2019-04-21
linux配置匿名ftp服务器,在Linux环境中使用vsftpd搭建ftp实现匿名上传详细配置 2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘 2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD 2019-04-21
.net core linux 桌面应用,C# dotnet core + AvaloniaUI 开发桌面软件,hello world 2019-04-21
linux tcp 113错误,linux系统报tcp_mark_head_lost错误的处理方法 2019-04-21
南昌工程学院c语言答案,南昌工程学院C语言程序设计基础课件第3讲运算符和表达式... 2019-04-21
python 阶乘怎么取出末尾的零_4个步骤,写出一个递归函数,看专业python工程师的骚操作... 2019-04-21
android aar保存图片文件异常_如何把PDF文件中的图片保存下来? 2019-04-21
python学画画_python学画画(下) 2019-04-21
云栖社区 mysql_【直播结束,已更新回放】PG、MySQL到底哪个好?云栖说这次请来五位专家撕了一下-阿里云开发者社区... 2019-04-21
老男孩mysql 百度云_英语语录:除了你,没人能掌控你的幸福 2019-04-21
mysql驱动多次执行问题_Laravel5.2队列驱动expire参数设置带来的重复执行问题 数据库驱动... 2019-04-21
mysql获取刚新增的数据库_如何取得刚插入数据库的数据的id mysql 2019-04-21
python将10到1递减_(Python)如何将3个递减列表合并成一个递减列表? 2019-04-21
python脚本怎么用来处理数据_长时间运行数据处理python脚本的程序结构 2019-04-21
python转成c 语言_将Python对象转换为C void类型 2019-04-21