2015蓝桥杯省赛B组----交换啤酒瓶

左手的ㄟ右手 2022-05-28 05:44 242阅读 0赞

交换瓶子

有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

> 很显然这里是贪心算法  
> 看上去很复杂 其实 挺简单的  
> *瓶子的编号 恰好是 从1开始 连续的 刚好 对应数组下标*  
> **那么就可以直接 将 此瓶子放到对应下标位置即可**

// 这里列举了用 5 个瓶子的 实例 , 对于N个瓶子来说 代码是一样的 此代码同样适用
         交换 啤酒瓶
        int num[5] = {
       5, 4, 3, 2, 1};
        // 1 4 3 5 2 . 1 5 3 4 2 . 1 2 3 4 5// 3次 
        int i = 0;
        int len = sizeof(num)/sizeof(num[0]);
        int index = -1; 
        int count = 0;
        for(i = 0; i < len; ){
            index = num[i]; 
            if(index - 1 != i){
       // 如果下标 和 瓶子编号不对应就 要交换 
                num[i] = num[index - 1];
                num[index - 1] = index;
                count ++;// 交换次数加一
            }else{
                i++;
            }   
        } 
        for(i = 0; i < len; i++)
        cout << num[i] << ", ";
        cout << "\n" << count << endl;