逆序数:在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。
如:
P 5 9 1 8 2 6 4 7 3
I 2 3 6 4 0 2 2 1 0
1前面比1大的有2个
2前面比2大的有3个
3前面比3大的有6个。。。。
1201:在permutation 和inversion之间转换。
思路:P-->I
双重循环,对每个数统计前面比它大的有几个
I-->P
双重循环。从最小的开始排起,每次从头扫描,给比它大的值留下空位。
#include<stdio.h>
#include<memory.h>
#include<iostream>
using namespace std;
int res[51];
int src[51];
void P2I(int n)
{
int count=0;
for(int i=1;i<=n;i++)
{
count=0;
for(int j=1;j<=n;j++)
{
if(src[j]>i)
count++;
else if(src[j]==i)
break;
}
res[i]=count;
}
}
void I2P(int n)
{
memset(res,0,sizeof(int)*51);
int count=0;
for(int i=1;i<=n;i++)
{
count=0;
for(int j=1;j<=n;j++)
{
if(res[j]==0)
count++;
if(count>src[i])
{
res[j]=i;
break;
}
}
}
}
int main()
{
int n;
char type;
while(1)
{
cin>>n;
if(n!=0)
{
cin>>type;
for(int i=1;i<=n;i++)
cin>>src[i];
if(type=='P')
P2I(n);
else if(type=='I')
I2P(n);
}
else
break;
for(int i=1;i<n;i++)
cout<<res[i]<<' ';
cout<<res[n]<<endl;
}
}
分享到:
相关推荐
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 3590 -3+1.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 3212 K-Nice.md
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
acm中zoj1002的可运行C++程序
zoj 2561 Order-Preserving Codes.md
包含了zoj700多道题目的源代码,在做题时可以参考
NULL 博文链接:https://weitch.iteye.com/blog/1006972
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够