hdu 1394 Minimum Inversion Number 逆序数/树状数组
2024-08-27 04:12:54
Minimum Inversion Number
Time Limit: 1 Sec Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=1394
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.
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
HINT
题意
这个区间可以变,就是可以把第一个数扔到最后去,然后这样变呀变,问这种变化下,最小的逆序数数是多少
题解:
啊,最大的数为n,把第一个数扔到最后,那么逆序数减少了num[i]-1,但是却增加了n-num[i],那就随便搞搞就好啦~
代码:
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 100001
#define mod 10007
#define eps 1e-9
const int inf=0x7fffffff; //无限大
/*
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
*/
//**************************************************************************************
int d[maxn];
int c[maxn];
int n;
int t;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int lowbit(int x)
{
return x&-x;
} void update(int x,int y)
{
while(x<=t)
{
d[x]+=y;
x+=lowbit(x);
}
}
int sum(int x)
{
int s=;
while(x>)
{
s+=d[x];
x-=lowbit(x);
}
return s;
}
int num[maxn];
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(d,,sizeof(d));
memset(num,,sizeof(num));
memset(c,,sizeof(c));
//n=read();
int ans=;
t=n;
for(int i=;i<n;i++)
{
num[i]=read();
num[i]++;
ans+=num[i]-sum(num[i]-)-;
update(num[i],);
}
int tmp=ans;
for(int i=;i<n;i++)
{
tmp+=n--*num[i]+;
ans=min(tmp,ans);
}
cout<<ans<<endl;
}
}
最新文章
- shiro在springmvc里面的集成使用【转】
- 初学c# -- 学习笔记(七) RichTextBox支持GIF
- ASP.NET MVC中使用highcharts 生成简单的折线图
- Laravel在不同的环境调用不同的配置文件
- CodeForces - 405C
- 执行shell脚本的几种方法及区别
- HDU 4706:Children&#39;s Day
- u-boot 之配置分析 (2)
- Linux有问必答:怎样解决“XXX is not in the sudoers file”错误
- Eclipse配置Flex开发环境(转)
- WEB-INF简介
- php-Mysql示例1
- Eclipse常用热键
- 设备MyEclipse6.5的maven
- WPF子窗体:ChildWindow
- centos7 部署openstf
- Matlab生成.exe可执行程序
- c语言贪吃蛇详解-2.画出蛇
- Hibernate 连接不同数据库的方言
- ntldr is missing