题目描述

蒙斯特有一个爱好 - 收集花样滑冰交易卡。

他的卡片收藏数量一直在增长，现在卡片数量很多，而且卡片在杂乱无章的放置着。

每张卡片上都有一个滑冰运动员的名字。

蒙斯特需要按字母顺序对卡片进行排序，这样他就可以在必要时在短时间内找到他想要的卡片。

但问题是手上的汗水会对卡片造成永久性损坏，所以蒙斯特不能直接自己上手整理这些卡片。

为了便于分类，蒙斯特请Horrible博士为他发明了一个分拣机器人。

然而，Horrible博士的机器人并不是免费的，在分拣过程中每当必须移动交易卡时，分拣机器人就会收取蒙斯特1美元的费用。

蒙斯特发现机器人的排序机制非常原始。

它从上到下扫描卡片组，每当它找到一个在字典顺序中比前一张卡靠前的卡时，它会将该卡向上移动至正确位置。

这个操作将收取1美元的费用，机器人会一直扫描至最后一张卡片，并一个接一个地移动卡片，直到所有卡片按字典顺序从上到下排序。

蒙斯特想知道使用机器人对他的牌组进行排序需要他支付多少费用。

样例

输入样例：
2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi


输出样例：
Case #1: 1
Case #2: 0

算法

(插入排序)

1. 使用getline()和getchar()
2. 插入排序，从第2个开始比较。
3. res ++的操作是在当cards[i]比cards[i - 1]小的时候执行的，所以要放在对应位置，一开始放错 了。。

时间复杂度

$O(n^2)$
本道题的时间复杂度是10的6次方

C++ 代码

#include <iostream>

using namespace std;

const int N = 110;

int T, n;
string cards[N];

int main()
{
    cin >> T;
    for(int c = 1; c <= T; c ++)
    {
        cin >> n;
        getchar();

        for(int i = 0; i < n; i ++) getline(cin, cards[i]);

        int res = 0;
        for(int i = 1; i < n; i ++)
            if(cards[i] < cards[i - 1])
            {
                for(int j = i; j; j --)
                    if(cards[j] < cards[j - 1])
                        swap(cards[j], cards[j - 1]);
                res ++;
            }

        printf("Case #%d: %d\n", c, res);
    }

    return 0;
}