[蓝桥杯 2016 省 B] 交换瓶子

2024-04-03 02:04
文章标签 交换 蓝桥 2016 瓶子

本文主要是介绍[蓝桥杯 2016 省 B] 交换瓶子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

[蓝桥杯 2016 省 B] 交换瓶子

题目描述

N N N 个瓶子,编号 1 ∼ N 1∼N 1N,放在架子上。

比如有 5 5 5 个瓶子:

2,1,3,5,4

要求每次拿起 2 2 2 个瓶子,交换它们的位置。

经过若干次后,使得瓶子的序号为:

1,2,3,4,5

对于这么简单的情况,显然,至少需要交换 2 2 2 次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入格式

第一行:一个正整数 N N N,表示瓶子的数目。

第二行: N N N 个正整数,用空格分开,表示瓶子目前的排列情况。

输出格式

输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。

输入输出样例
输入
5
3 1 2 5 4
输出
3
输入
5
5 4 3 2 1
输出
2
数据范围
  • N ≤ 10000 N \leq 10000 N10000

解法:贪心

对于 a [ i ] a[i] a[i] :

  • 如果 a [ i ] a[i] a[i] 在其正确的位置上,即 a [ i ] = i a[i] = i a[i]=i,那就跳过;

  • 对于 a [ i ] a[i] a[i] 不在它正确的位置上,即 a [ i ] ≠ i a[i] \neq i a[i]=i,就要从 [ i + 1 , n ] [i + 1, n] [i+1,n] 中找到元素 i i i 的位置 j j j,即 a [ j ] = i a[j] = i a[j]=i。此时需要交换 ( a [ i ] , a [ j ] ) (a[i], a[j]) (a[i],a[j]),交换次数加一。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

C++代码:

#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <unordered_set>
#include <set>
#include <algorithm>using namespace std;
using LL = long long;void solve(){int n;cin>>n;vector<int> a(n + 5);for(int i = 1;i <= n;i++) cin>>a[i];int ans = 0;for(int i = 1;i <= n;i++){if(a[i] != i) //不在正确的位置上,需要交换{ans++;for(int j = i + 1;j <= n;j++){if(a[j] == i){swap(a[i], a[j]);break;}}}}cout<<ans<<'\n';}int main(){int t = 1;//cin>>t;while(t--){solve();}return 0;
}

Java代码:

import java.io.*;
import java.util.*;public class Main
{static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws Exception{int n = Integer.parseInt(in.readLine().trim());String[] str = in.readLine().split(" ");int[] a = new int[n + 5];for(int i = 0;i < n;i++){a[i + 1] = Integer.parseInt(str[i]);}int ans = 0;for(int i = 1;i <= n;i++){if(a[i] != i){ans++;for(int j = i + 1;j <= n;j++){if(a[j] == i){int temp = a[i];a[i] = a[j];a[j] = temp;break;}}}}System.out.println(ans);}
}

这篇关于[蓝桥杯 2016 省 B] 交换瓶子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/871643

相关文章

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

不设临时变量交换a,b的值

常规的做法: int tmp = a; a = b; b = tmp; 不设中间变量的方法: a = a + b; b = a - b; a = a - b;

交换两个变量数值的3种方法

前言:交换两个数值可不是"a = b,b = a"。这样做的话,a先等于了b的值;当“b = a”后,因为此时a已经等于b的值了,这个语句就相当于执行了b = b。最终的数值关系就成了a == b,b == b。 下面教给大家3种交换变量数值的方法: 目录 1. 中介法 2. 消和法 3. 异或法 4. 总结 1. 中介法 中介法(又称 临时变量法 或 酱油法),其中心

用异或交换两个整数的陷阱

前面我们谈到了,可用通过异或运算交换两个数,而不需要任何的中间变量。 如下面: void exchange(int &a, int &b) {     a ^= b;     b ^= a;     a ^= b; } 然而,这里面却存在着一个非常隐蔽的陷阱。 通常我们在对数组进行操作的时候,会交换数组中的两个元素,如exchang(&a[i], &b[j]),

实践课堂|2016成都站|报名开始啦!

Hi,QingCloud 的小伙伴们,欢迎参加史上最有营养的云知识讲堂。 QingCloud 实践课堂系列开始于 2014 年末,在深圳、上海、广州、成都、杭州、北京六个城市,QingCloud 的研发工程师们同近千名 CIO 、架构师、开发者、运维工程师……分享了 QingCloud 的技术理念、功能特性和使用技巧,还有来自人民网、融云、泰捷视频、杏树林、友好速搭、百姓网、冰点、顺丰速运、洋葱

找不同-第15届蓝桥省赛Scratch初级组真题第4题

[导读]:超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第183讲。 如果想持续关注Scratch蓝桥真题解读,可以点击《Scratch蓝桥杯历年真题》并订阅合集,查阅教程更方便。 第15届蓝桥杯省赛已于2024年8月24日落下帷幕,编程题一共有5题,分别如下: 猪八戒落地 游乐场 画西瓜 找不同 消

常见的交换变量的三种方法

常见的交换变量的三种方法     在项目中,两个变量之间交换位置在常见不过了,如进行排序。     下面说下常见的三中变量交换模式。 1、定义中间变量 #include <stdio.h>int main(){int a=9, b=3; //方法一://交换两个变量值的常规做法int tmp=a;a=b;b=tmp;printf("a=%d b=%d\n",a,b);

【蓝桥杯嵌入式(一)程序框架和调度器】

蓝桥杯嵌入式(一)程序框架和调度器 序、代码命名规则零、STM32和8051⼀、软件及环境安装⼆、⼯程框架搭建1.时钟配置2、SYS配置3、⼯程配置4、NVIC配置5.、Keil配置 三、系统初始化四、任务调度器 链接: 视频出处 序、代码命名规则 以下是一些常见的举例 零、STM32和8051 链接: 8位和32位单片机最本质区别 ⼀、软件及环境安装