首页 > 其他分享 >xtu oj 逆序数(小数据) //冒泡排序

xtu oj 逆序数(小数据) //冒泡排序

时间:2024-10-31 11:15:51浏览次数:3  
标签:xtu xi oj int 样例 冒泡排序 num 序列 序数

题目描述

给你一个序列x1,x2,…,xn,如果数对< xi,xj >,其中i< j,而xi> xj我们称之为逆序数对。 一个序列的逆序数对的数目,称为这个序列的逆序数。 比如说序列 3 1 2 ,逆序数对为 <3,1>和<3,2>,所以这个序列的逆序数为2。 现在给你一个数字序列,请求其逆序数。

输入

每个样例为两行,第一行为一个整数n(n≤1,000),表示序列中数字的个数,如果n为0,则表示输入结束,不需要处理。 第二行是n个整数xi,0≤xi≤100,000。输入数据保证序列中没有相同整数。

输出

每行输出一个整数,表示其序列数。

样例输入
3
3 1 2
4
1 2 3 4
0

样例输出
2
0

 AC代码如下

#include<stdio.h>
int main()
{
	int n;
	
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		int num=0;
		int a[100001];
		int i;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<n-i;j++)
			{
				if(a[j]>a[j+1])
				{
					int temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
					num++;
				}	
			}
		}
		printf("%d\n",num);
		
		
	}
	return 0;
}

标签:xtu,xi,oj,int,样例,冒泡排序,num,序列,序数
From: https://blog.csdn.net/literature_art/article/details/143335704

相关文章

  • Invalid classpath container: 'JUnit 4' in project
    安装eclipse2024-06后,打开plug-in工程报错:Invalidclasspathcontainer:'JUnit4'inproject解决方案一:在网上搜索一番,找到一篇大佬的解决方案https://aigcdaily.cn/news/b24u9zo1809ojin/在文章中大佬给出了明确的解决方案:替换org.eclipse.jdt.junit.core_3.13.200.v202405......
  • QOJ #9317. Rivals
    题面传送门直接做显然不太好做,考虑转化成每次都从\(n\)个怪中随机挑一个出来打,但是只有挑到还有血量的怪才算入“打了一次”。使用生成函数来刻画这个东西:当打了一次,乘上一个\(y\),打了有效的一次,乘上一个\(x\)。枚举最后一次有效攻击打到了哪个身上,则每个怪的EGF就是\[x^......
  • emoji编码和长度校验
    背景:最近有个需求,在校验输入内容中要校验字符长度,但是里面包含了支持emoji类型在length计数时惊了我,知识盲区--》补课问题描述:1.校验规则:最大12个中文字符,24个英文字符,支持emoji、数字、标点符号2.console.log('......
  • 冒泡排序的学习与使用
    一.什么是冒泡数列?1.冒泡数列就是元素按ASCII码值从小到大排序的数列,由于很像水中泡泡向上冒出的形态,所以叫冒泡数列,如图:        二.如何将一个数列转换成冒泡数列?     答:使用冒泡排序即可将一个乱序的数列转换成冒泡数列。    冒泡排序即按ASCI......
  • POJ2240-Arbitrage
    继续刷邝斌飞最短路专题POJ2240(TimeLimit:1000MS、MemoryLimit::65536K)洛谷(时间限制:242ms、内存限制:1.46GB,tmd惊到我了) —— 洛谷买一送一(时间限制:3s)风格好爱,很有梯度,深入浅出。之前搜索专题里着火问题重复出现了、倒水问题重复出现了,这里汇率套利问题重复出现了读......
  • 将POJO类的成员全部设置为public多省事儿
    最近浏览一个项目的代码时发现,其中有一些以前提交的编码,定义的一些类(不管他是POJO、DTO、DAO、PO、BO、VO、QO、ENTITY还是就是个对象,不重要。总之就是数据传输对象。),这些类他的写法非常的潇洒,属性全部是public的,没有任何的get、set方法,看起来非常干净、整洁。比如基本都像下面这......
  • 每日OJ题_牛客_AB20走迷宫_BFS_C++_Java
    目录牛客_AB20走迷宫_BFS题目解析C++代码Java代码牛客_AB20走迷宫_BFS走迷宫_牛客题霸_牛客网(nowcoder.com)描述:        给定一个n×m的网格,在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物,放有......
  • python 入门九大排序:1冒泡排序2插入排序3选择排序4快速排序5归并排序6堆排序7计数排序
    1冒泡排序:冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。代码如下:importnumpyasnpdefbubbling(arr):n=len(arr)foriinrange(n-1):forjinrange(n-i-1):ifarr[j......
  • 【OJ题解】C++ 把字符串转换成整数
    ......
  • ybtoj题解索引
    密码:sunxuhetai2009第一章-递推算法A.错排问题B.传球游戏C.数的划分D.栈的问题E.求f函数F.划分数列G.无限序列......