交换瓶子---蓝桥杯

简介: 交换瓶子---蓝桥杯

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


比如有5个瓶子:

2 1 3 5 4


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

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

1 2 3 4 5


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


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


输入格式为两行:

第一行: 一个正整数N(N<10000), 表示瓶子的数目

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


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


例如,输入:

5

3 1 2 5 4


程序应该输出:

3


再例如,输入:

5

5 4 3 2 1


程序应该输出:

2


资源约定:

峰值内存消耗 < 256M

CPU消耗 < 1000ms

思路:找规律+枚举 枚举每一个数,如果该位置上不是当前的数,则查找目标数的位置,然后与当前位置的数进行交换.统计交换次数,即为所求.

有时候编程思维还是很重要的,慢慢培养吧,自己本以为是冒泡或者快排,但最后发现不是.


参考代码

#include<bits/stdc++.h>
using namespace std;
int n,pos,cnt,arr[10000+10];
int getPos(int m){//查找元素位置 
  for(int i = 1; i <= n; i++){
    if(arr[i]==m){
      return i;
    }
  }
  return -1;
}
int main()
{
  cin>>n;
  for(int i = 1; i <=n; i++){
    cin>>arr[i];
  }
  for(int i = 1; i <= n; i++){
    if(i!=arr[i]){
      pos = getPos(i);
      swap(arr[i],arr[pos]);
      cnt++;
    } 
  } 
  cout<<cnt<<endl;
  return 0;
 } 
相关文章
|
7月前
|
算法
算法每日一题---两数之和
算法每日一题---两数之和
32 0
|
6月前
|
算法 图计算
力扣经典150题第十六题:接雨水
力扣经典150题第十六题:接雨水
32 0
|
7月前
|
人工智能
888. 公平的糖果棒交换(力扣)
888. 公平的糖果棒交换(力扣)
|
7月前
|
算法
2024春晚纸牌魔术原理----环形链表的约瑟夫问题
2024春晚纸牌魔术原理----环形链表的约瑟夫问题
|
算法
【LeetCode力扣】42. 接雨水
【LeetCode力扣】42. 接雨水
80 0
[蓝桥杯 2016 省 B] 交换瓶子
[蓝桥杯 2016 省 B] 交换瓶子
61 0
每日一题---力扣算法题 401. 二进制手表
每日一题---力扣算法题 401. 二进制手表
每日一题---力扣算法题 401. 二进制手表
|
机器学习/深度学习 人工智能
【第十五届蓝桥杯备赛(bushi,写文凑个数)】蓝桥OJ---排列序数
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 DFS
99 0
|
机器学习/深度学习 算法
【第十五届蓝桥杯备赛(bushi,写文凑个数)】蓝桥OJ---长草
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 BFS Flood Fill算法
186 0
|
人工智能
凑算式---蓝桥杯
凑算式---蓝桥杯
凑算式---蓝桥杯