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

news/2024/4/25 17:55:54

题目链接

[蓝桥杯 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);}
}

https://www.xjx100.cn/news/3366551.html

相关文章

前后端开发之——文章分类管理

原文地址&#xff1a;前后端开发之——文章分类管理 - Pleasure的博客 下面是正文内容&#xff1a; 前言 上回书说到 文章管理系统之添加文章分类。就是通过点击“新建文章分类”按钮从而在服务端数据库中增加一个文章分类。 对于文章分类这个对象&#xff0c;增删改查属于配…

人工智能(pytorch)搭建模型25-基于pytorch搭建FPN特征金字塔网络的应用场景,模型结构介绍

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能(pytorch)搭建模型25-基于pytorch搭建FPN特征金字塔网络的应用场景&#xff0c;模型结构介绍。特征金字塔网络&#xff08;FPN&#xff09;是一种深度学习模型结构&#xff0c;主要应用于目标检测任务中&am…

springboot基本使用八(mbatisplus+filter实现登录功能)

mybatisplus依赖&#xff1a; <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.4.2</version> </dependency> mysql依赖&#xff1a; <dependency><grou…

147.【2024Java八股-全网最全-10w字】

100道Java经典面试题 (一)、准备篇1.HR如何筛选简历?2.部门负责人如何筛选简历?3.简历模块布局4.应届生如何找到合适的练手项目?5.深入学习哪些业务模块呢?6.Java程序员的面试过程 (二)、Redis篇1.redis经常使用在哪些场景?2.Redis进行查询的流程是什么?3.什么是缓存穿透…

【Servlet】thymeleaf快速入门

文章目录 一、thymeleaf介绍二、入门案例 一、thymeleaf介绍 Thymeleaf&#xff1a;视图模板技术 在index.html页面上加载java内存中的fruitList数据&#xff0c;这个过程我们称之为渲染&#xff08;render&#xff09;。 thymeleaf是用来帮助我们做视图渲染的一个技术。 二…

C语言 | Leetcode C语言题解之第6题Z字形变换

题目&#xff1a; 题解&#xff1a; char * convert(char * s, int numRows){int n strlen(s), r numRows;if (r 1 || r > n) {return s;}int t r * 2 - 2;char * ans (char *)malloc(sizeof(char) * (n 1));int pos 0;for (int i 0; i < r; i) { // 枚举矩阵的…

数据分析之POWER BI Desktop可视化应用案列

在power bi中导入数据 导入前期建好的模型 简单介绍&#xff08;power bi desktop&#xff09; 将右边字段全部展开 各类数据 所作的模型 在excel中是单向的&#xff0c;power bi 中可以是双向的 右键单击----点击属性 选择两个---在两个方向上应用安全筛选器 变为双向的…

MySQL-linux安装-万能RPM法

一、MySQL的Linux版安装 1、 CentOS7下检查MySQL依赖 1. 检查/tmp临时目录权限&#xff08;必不可少&#xff09; 由于mysql安装过程中&#xff0c;会通过mysql用户在/tmp目录下新建tmp_db文件&#xff0c;所以请给/tmp较大的权限。执行 &#xff1a; chmod -R 777 /tmp2. …