Arranging Books

题目描述

Valentina wants books on a shelf to be arranged in a particular way. Every time she sees a shelf of books, she rearranges the books so that all the large books appear on the left,followed by all the medium-sized books, and then all the small books on the right. She does this by repeatedly choosing any two books and exchanging their locations. Exchanging the locations of two books is called a swap. Help Valentina determine the fewest number of swaps needed to arrange a shelf of books as she wishes. Valentina希望书架上的书能以一种特殊的方式排列。每次她看到书架上的书，她都会把书重新排列，这样所有的厚书都出现在左边，然后是所有的中等书，然后是右边所有的薄书。她通过反复选择任意两本书并交换它们的位置来做到这一点。交换两本书的位置称为交换。

帮助Valentina确定根据自己的意愿安排书架所需的最少交换次数。

输入格式

The input will consist of exactly one line containing at least one character. The following table shows how the available 15 marks are distributed.  输入将由恰好包含至少一个字符的一行组成。 下表显示了可用的15个标记的分布情况。

输出格式

Output a single integer which is equal to the minimum possible number of swaps needed to arrange the books so that all occurrences of L come first, followed by all occurrences of M,and then all occurrences of S. 输出一个整数，该整数等于排列账簿所需的最小可能交换次数，使所有出现的L先出现，然后是所有出现的M，然后是S。

LMMMS

0

LLSLM

2

提示

#### 数据范围与提示 Explanation of Output for Sample Input 1 The books are already arranged according to Valentina’s wishes. Explanation of Output for Sample Input 2 By swapping the S and M, we end up with LLMLS. Then the M can be swapped with the L to its right. This is one way to use two swaps to arrange the books as Valentina wants them to be. It is not possible to use fewer swaps because both S and M need to be moved but using one swap to exchange them does not leave the books arranged as Valentina wants them to be.

来源

童程童美