题目描述

扫描卡片组。每当它找到一个在字典顺序中比前一张卡靠前的卡时，它会将该卡向上移动至正确位置。一次一美元
蒙斯特想知道使用机器人对他的牌组进行排序需要他支付多少费用

样例

2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi
输出：
Case #1: 1
Case #2: 0

算法1

(插入排序) $O(n^2)$

时间复杂度

参考文献

C++ 代码

//插入排序
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int n;
string cards[N]; //卡片
int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; C++)
    {
        cin >> n;
        getchar(); //把数前面的回车读掉，避免读空(~~格~~回车)气
        for (int i = 0; i < n; i++) getline(cin, cards[i]); //读入，有空格所以不能cin，而是getline

        int res= 0; //题意所求 操作数
        for (int i = 1; i < n; i++) //模拟
            if (cards[i] < cards[i - 1])
            {
                for (int j = i; j; j --) // j即 j = 0
                    if (cards[j] < cards[j - 1])
                        swap(cards[j], cards[j - 1]);
                res ++;
            }
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

时间复杂度

参考文献

Python 代码

# O(n^2) 插入排序
# 暴力模拟
# 读入字符串可能包含空格。c++ => get.line() 不安全 c++17里删掉了get
def count(nums):
    res = 0 #需要支付费用，即（指一整套）操作次数。即一共换了几个数
    for i in range(1, len(nums)):
        if nums[i - 1] > nums[i]:
            for j in range(i, 0, -1): #逆序遍历
                """
                # if nums[j] < nums[j - 1]: #如果当前字比之前那个字小，将它们交换。
                """
                if nums[j - 1] > nums[j]: # 如果前一个数比这个数字典序大，将它们交换。
                    nums[j - 1], nums[j] = nums[j], nums[j - 1] #所以最后得到一个升序数据
            res += 1
    return res

if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        n = int(input())
        table = [input() for _ in range(n)]
        res = count(table)
        print(f'Case #{i + 1}: {res}') #f'写法

作者：查猪字幕组
链接：https://www.acwing.com/activity/content/code/content/917297/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。