首页 > 其他分享 >P1116 车厢重组 洛谷

P1116 车厢重组 洛谷

时间:2024-03-16 18:29:05浏览次数:17  
标签:洛谷 P1116 temp int 样例 ## 车厢 ans

附加AC代码噢噢噢噢噢噢噢噢噢噢噢噢噢噢噢噢哦哦哦!

# 车厢重组

## 题目描述

在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢,如果将桥旋转 180

 度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后,火车站决定将这一工作自动化,其中一项重要的工作是编一个程序,输入初始的车厢顺序,计算最少用多少步就能将车厢排序。

## 输入格式

共两行。  

第一行是车厢总数 $N( \le 10000)$。
  
第二行是 N 个不同的数表示初始的车厢顺序。  
(**注**:实际上数据中并不都在同一行,有可能分行输入)

## 输出格式

一个整数,最少的旋转次数。

## 样例 #1

### 样例输入 #1

```
4
4 3 2 1
```

### 样例输出 #1

```
6
```

用冒泡排序哦!!

1号方法

#include <iostream>
using namespace std;
int main() {
    int a[1001];
    int n;
    int temp,ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
}
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(a[j]>a[j+1]){
               swap(a[j],a[j+1]);
                ans++;
		}
	}
}
    cout<<ans<<endl;
  return 0;
}

2号方法 

#include <iostream>
using namespace std;
int main() {
    int a[1001];
    int n;
    int temp,ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
}
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(a[j]>a[j+1]){
                temp =a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                ans++;
		}
	}
}
    cout<<ans<<endl;
  return 0;
}

标签:洛谷,P1116,temp,int,样例,##,车厢,ans
From: https://blog.csdn.net/NOIPwjy2011/article/details/136765973

相关文章

  • 洛谷 P2241 统计方形(数据加强版)
    一些文字说明 我们首先来定义一个东西,在我这里,矩形的长是指横向的边的长度,宽是指纵向的边的长度,宽可以比长还长。 由题意可知,题目要求我们求出在一个m*n的矩形中求出其包含的长方形的数量和正方形的数量,而长方形和正方形都是矩形,那么我们就是要求其包含的矩形的数量,可以......
  • 洛谷题解 - B3850 [GESP202306 四级] 幸运数
    目录题目描述输入格式输出格式样例#1样例输入#1样例输出#1代码题目描述小明发明了一种“幸运数”。一个正整数,其偶数位不变(个位为第111位,十位为第......
  • 洛谷题单指南-二叉树-P1030 [NOIP2001 普及组] 求先序排列
    原题链接:https://www.luogu.com.cn/problem/P1030题意解读:已知中序、后序,求先序。解题思路:与洛谷题单指南-二叉树-P1827[USACO3.4]美国血统AmericanHeritage非常类似,不在介绍过程,直接给出代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;stringin,post......
  • 洛谷 P5018 对称二叉树
    题目背景NOIP2018普及组T4题目描述一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:二叉树;将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。下图中节点内的数字为权值,节点外的 idid 表示节点编号。现在给出一棵二叉树,希望你找出......
  • 洛谷 B3625 迷宫寻路
    本道题需要注意:如果孩子的起始位置就是‘#’,那孩子就无路可走,出不来了。所以需要特判一下,代码如下:(这是废话,不需要特判,注意题目要求)if(ch[1][1]=='#'){ printf("No\n"); }注意边界条件:if(nx<1||nx>n||ny<1||ny>m){ continue; } if(vis[nx][ny]==1){ cont......
  • 洛谷 P3596 [POI2015] MOD 题解
    题意简述给定一棵树,求断掉一条边再连上一条边所得的新树直径最小值和最大值,以及相应方案(你可以不进行任何操作,即断掉并连上同一条边)。题目分析假设我们枚举断掉某一条边,得到了两棵树,并且知道它们的直径分别为\(d_0,d_1\),那么如何连接一条边让新树的直径最大/最小呢?最大:显......
  • 洛谷 P3261 [JLOI2015] 城池攻占 题解
    题目分析其他人要么倍增,要么左偏树,那我就来讲讲朴实无华的dfs序加上线段树的做法。首先发现题目中明确指出了作乘法的时候一定是乘上一个大于零的数,这是为什么呢?首先把可以占领当前城池的战斗力的不等式列出来:\[h_j\le\left\{\begin{array}{c}s_i\timesv_j&&{a_j=......
  • 洛谷题单指南-二叉树-P5076 【深基16.例7】普通二叉树(简化版)
    原题链接:https://www.luogu.com.cn/problem/P5076题意解读:此题本质上是要实现一个二叉搜索树的功能。解题思路:从数据规模10^4来看,只要复杂度在n^2范围内基本上是可以通过的,下面给出两种做法:1、有序数组法对应5个操作的实现逻辑如下:操作一:查x的排名。直接通过二分查找>=x的第......
  • C语言:洛谷数组题目(2)(冰雹猜想,校门外的树,旗鼓相当的对手)
    目录1.前言2.三则题目1.冰雹猜想1.题目描述2.输入格式3.输出格式4.题解2.校门外的树1.题目描述2.输入格式3.输出格式4.题解3.旗鼓相当的对手1.题目描述2.输入格式3.输出格式4.题解3.小结1.前言今天小蒟蒻继续为大家分享洛谷数组题单题解,一共三道题,希望大......
  • 洛谷题单指南-二叉树-P4913 【深基16.例3】二叉树深度
    原题链接:https://www.luogu.com.cn/problem/P4913题意解读:计算二叉树的深度解题思路:首先介绍二叉树的存储方式,对于本题,直接用数组模拟,数组的下标即节点号structnode{intl,r;}tree[N];tree[i].l存的是节点i的左子结点,tree[i].r存的是节点i的右子节点。计算深度至......