题目描述
蒙斯特有一个爱好 - 收集花样滑冰交易卡。
他的卡片收藏数量一直在增长,现在卡片数量很多,而且卡片在杂乱无章的放置着。
每张卡片上都有一个滑冰运动员的名字。
蒙斯特需要按字母顺序对卡片进行排序,这样他就可以在必要时在短时间内找到他想要的卡片。
但问题是手上的汗水会对卡片造成永久性损坏,所以蒙斯特不能直接自己上手整理这些卡片。
为了便于分类,蒙斯特请Horrible博士为他发明了一个分拣机器人。
然而,Horrible博士的机器人并不是免费的,在分拣过程中每当必须移动交易卡时,分拣机器人就会收取蒙斯特1美元的费用。
蒙斯特发现机器人的排序机制非常原始。
它从上到下扫描卡片组,每当它找到一个在字典顺序中比前一张卡靠前的卡时,它会将该卡向上移动至正确位置。
这个操作将收取1美元的费用,机器人会一直扫描至最后一张卡片,并一个接一个地移动卡片,直到所有卡片按字典顺序从上到下排序。
蒙斯特想知道使用机器人对他的牌组进行排序需要他支付多少费用。
样例
输入样例:
2
2
Oksana Baiul
Michelle Kwan
3
Elvis Stojko
Evgeni Plushenko
Kristi Yamaguchi
输出样例:
Case #1: 1
Case #2: 0
算法
(堆排序) $O(nlogn)$
建立一个大根堆,每次与堆顶部比较,如果小于堆顶部,说明要进行移动操作,结果加一
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int t;
cin >> t;
for (int tt = 1; tt <= t; ++tt)
{
int n;
cin >> n;
getchar(); // 吃掉一个回车
priority_queue<string> bheap;
int res = 0;
for (int i = 0; i < n; ++i)
{
string s;
getline(cin, s);
if (!bheap.empty())
{
if (s < bheap.top()) res++;
}
bheap.push(s);
}
cout << "Case #" << tt << ": " << res << endl;
}
return 0;
}