给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目
输入:第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。
输出:两行,第一行为所有逆序对总数,第二行为本质不同的逆序对总数。
样例输入:
4
3
2
3
2
样例输出:
3
1
数据范围:N<=105。Ai<=105。时间限制为1s。
哪位大牛帮下忙,讲下怎么用归并排序或树状数组做,主要是第二问,麻烦讲详细的,有程序的最好,PASCAL和C++的都可以
一道编程题:求逆序对的个数
答案:4 悬赏:60 手机版
解决时间 2021-04-07 11:22
- 提问者网友:捧腹剧
- 2021-04-07 05:29
最佳答案
- 五星知识达人网友:怙棘
- 2021-04-07 05:39
#include<stdio.h>
#define N 105
void main()
{
int n,i,j,k=0,p,m=0;
int a[20];
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
getchar();
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
k++;
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]=a[j])
{
for(p=j+1;p<n;p++)
a[p-1]=a[p];
n--;
}
}
for(i=0;i<p;i++)
for(j=i+1;j<p;j++)
{
if(a[i]>a[j])
m++;
}
printf("%d\n%d",k,m);
}//呵呵,我只会用c写,不过结果是对的。
#define N 105
void main()
{
int n,i,j,k=0,p,m=0;
int a[20];
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
getchar();
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
k++;
}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]=a[j])
{
for(p=j+1;p<n;p++)
a[p-1]=a[p];
n--;
}
}
for(i=0;i<p;i++)
for(j=i+1;j<p;j++)
{
if(a[i]>a[j])
m++;
}
printf("%d\n%d",k,m);
}//呵呵,我只会用c写,不过结果是对的。
全部回答
- 1楼网友:猎心人
- 2021-04-07 08:15
前面改成int main(),如果测试程序有时间限制的话,这个算法不够优化,时间超出限制,不过改之后是可以运行的
- 2楼网友:摆渡翁
- 2021-04-07 07:21
6分之一,把26个数看成4个数来计算,
得出的答案是一样的,
就是六分之一
- 3楼网友:轻雾山林
- 2021-04-07 06:06
6分之一,把26个数看成4个数来计算,
得出的答案是一样的,
就是六分之一
再看看别人怎么说的。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯