文章

39

粉丝

74

获赞

1

访问

18.0k

头像
最少交换次数 题解:
P1853 北京师范大学2019年机试题
发布于2024年3月13日 16:29
阅读数 471

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
    int n;
    int res[1000];
    scanf("%d",&n);
    int count=0;
    for(int i=1;i<=n;i++)scanf("%d",&res[i]);
    int out[1000]={0};
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(res[j]>res[i])out[res[i]]++;
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",out[i]);
        count+=out[i];
    }
    printf("\n");
    printf("%d",count);

    return 0;
}

逆序列可以理解为一个单独的数组,aj表示在原数组中j前面大于j的个数

逆序数可以理解为逆序列的和

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发