P10110: 排队
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【问题描述】
钱伯斯夫人总是让她的班级学生的身高顺序排好队(最矮的排在队伍前面)。每年九月都会有整整20个三年级新生入学，他们的身高都不一样。在最初的几天里，要花很长时间让孩子们保持身高顺序，因为没有人知道他们应该排在队伍的哪个位置。今年，钱伯斯决定尝试一种新方法，以尽量减少这种秩序混乱。一名学生将被选为第一个排队的人。然后，选择另一个学生，他会在队列中找到第一个比他高的人，站在那个人的前面，从而使他后面的所有学生退后一步，腾出空间。如果没有一个学生比他高，那么他就会站在队伍的最后。这个过程持续进行，一次一个学生，直到所有的学生都排好队，这时学生将按照身高顺序排好队。
对于这个问题，您将编写一个程序，计算给定班级的学生在排序过程中退后的总步数。
【输入】
输入的第一行包含一个整数P， (1≤
P≤
1000)，即后续数据集的个数。每个数据集应进行相同且独立的处理。
每个数据集由单行输入组成。它包含数据集编号K，后面跟着20
由单个空格分隔的非负唯一整数。这20个整数代表班上每个学生的身高(以毫米为单位)。
【输出】
对于每个数据集，都有一行输出。单个输出行包括数据集编号K，后跟一个空格，后跟退后的总步数。
【输入采样1】
4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919
【输出采样1】
1 0
2 190
3 19
4 171
【样例输入】复制
4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919
【样例输出】 复制
1 0
2 190
3 19
4 171