HDU 1394 逆序数 线段树单点跟新 | 暴力
2024-10-19 21:11:29
Minimum Inversion Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19575 Accepted Submission(s): 11756
Problem Description
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
题意:
求每次将第一个数字放置到最后的逆序数,一共有n个逆序数,从这里面选取最小的一个。
思路:
1.暴力
将初始序列的逆序数求出来,之后的逆序数可以推导出来,假设得到了第一个逆序数 num。此时要将第一个数字data[i]放置到最后一个,那么num就要减去该数的值,重新产生了多少个逆序对呢?产生了n-data[i]-1个。就是序列中比data[i]大的数的个数。这个很容易推导出来。
代码:
求每次将第一个数字放置到最后的逆序数,一共有n个逆序数,从这里面选取最小的一个。
思路:
1.暴力
将初始序列的逆序数求出来,之后的逆序数可以推导出来,假设得到了第一个逆序数 num。此时要将第一个数字data[i]放置到最后一个,那么num就要减去该数的值,重新产生了多少个逆序对呢?产生了n-data[i]-1个。就是序列中比data[i]大的数的个数。这个很容易推导出来。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=50005;
int ans[maxn];
int main() {
int n;
while(~scanf("%d",&n)) {
for(int i=0;i<n;++i) {
scanf("%d",&ans[i]);
}
int sum=0;
for(int i=0;i<n-1;++i) {
for(int j=i+1;j<=n-1;++j) {
if(ans[i]>ans[j]) sum++;
}
}
int result=sum;
for(int i=0;i<n-1;++i) {
sum=sum-ans[i]+(n-ans[i]-1);
result=min(result,sum);
}
printf("%d\n",result);
}
return 0;
}
2.用线段树来做。
有了上面的推导,只要求出第一个,剩余的工作就变的简单了。
再用线段树求原始序列的时候要反向思维,求每一个数之前的序列中比自身大的个数。
假设现在给出一个序列是 : 4 3 1 5 0 2
我们在一边度数据的过程中计算逆序对的个数。初始话每个线段树的结点值都赋值为0。
先读到5,查询4-(n-1)区间即4-4有没有出现比4大的,没有,返回0。查询完成之后将该节点插入线段树。
再读到3,查询3-(n-1)区间有没有比3大的,返回1,将3插入。再将3插入线段树。以此类推...这样我们得到如下结果:
4 : 0
3 : 1(4)
1 : 2(3,4)
5 : 0
0 : 4(1,3,4,5)
2 : 3(3,4,5)
该序列的逆序数就是0+1+2+0+4+3=10。与我们求一般求逆序数时得到的结果相同。
注意是0-n-1的序列,建树注意下标
代码:
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn=5005;
int sum[maxn<<2];
int data[maxn];
void pushup(int rt) {
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l, int r, int rt) {
sum[rt]=0;
if(l==r)return;
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int val, int l, int r, int rt) {
if(l==r) {
sum[rt]++;return;
}
int mid=(l+r)>>1;
if(val<=mid) update(val,lson);
else update(val,rson);
pushup(rt);
}
int query(int L, int R, int l, int r, int rt) {
if(L<=l&&r<=R) {
return sum[rt];
}
int mid=(l+r)>>1,cnt=0;
if(L<=mid) cnt+=query(L,R,lson);
if(R>mid) cnt+=query(L,R,rson);
return cnt;
}
int main() {
int n;
while(~scanf("%d",&n)) {
int result,temp=0;
build(0,n-1,1);
for(int i=0;i<n;++i) {
scanf("%d",&data[i]);
temp+=query(data[i],n-1,0,n-1,1);
update(data[i],0,n-1,1);
}
result=temp;
for(int i=0;i<n;++i) {
temp=temp-data[i]+(n-1-data[i]);
result=min(result,temp);
}
printf("%d\n",result);
}
return 0;
}
最新文章
- python 数据类型 -- 元组
- sqlite简单使用
- jquery CRUD一个元素class属性
- Html Mailto标签详细使用方法
- iOS之 kamailio-4.3.4sip服务器搭建-mac
- php 上传大文件主要涉及配置upload_max_filesize和post_max_size两个选项
- UVa 253 Cube paiting
- c#自动更新+安装程序的制作 (转)
- 【C#】动态加载dll程序集
- QT 4.7.6 驱动 罗技C720摄像头
- Unity3D方法来隐藏和显示对象
- Myeclipse 创建 Web Maven项目
- JavaScript事件与例子(三)
- 一脸懵逼学习基于CentOs的Hadoop集群安装与配置
- html5 canvas画布尺寸与显示尺寸
- 获取select中的值
- iOS——系统提供的dispatch方法
- SpringMVC(九):SpringMVC 处理输出模型数据之ModelAndView
- C语言 递归 汉诺塔问题 最大公约数问题
- Azure Load Balancer : 支持 IPv6
热门文章
- LeetCode 485. Max Consecutive Ones (最长连续1)
- 用C写的计算运行时间
- Windows环境下多线程编程原理与应用读书笔记(1)————基本概念
- VS2012 C#生成DLL并调用
- JAVAscript学习笔记 js句柄监听事件 第四节 (原创) 参考js使用表
- PHP面向对象摘要
- PHPMailer 发送邮件(二)
- ASP.NET Core 2.0 集成测试无法执行的问题
- 面向亿万级用户的QQ一般做什么?——兴趣部落的Web同构直出分享
- 【吐槽】关于256个 class可以覆盖一个id的问题