UVA Height Ordering

题目描述

Mrs. Chambers always has her class line up in height order (shortest at the front of the line). Every September a new class of exactly 20 3rd graders arrive, all of different height. For the first few days it takes a long time to get the kids in height order, since no one knows where they should be in the line.
Needless to say, there is quite a bit of jockeying around. This year Mrs. Chambers decided to try a new method to minimize this ordering chaos. One student would be selected to be the first person in line. Then, another student is selected and would find the rst person in the line that is taller than him,and stand in front of that person, thereby causing all the students behind him to step back to make room. If there is no student that is taller, then he would stand at the end of the line. This process continues, one student at-a-time, until all the students are in line, at which point the students will be lined up in height order.
For this problem, you will write a program that calculates the total number of steps taken back during the ordering process for a given class of students.

输入

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input. It contains the data set number, K, followed by 20 non-negative unique integers separated by a single space. The 20 integers represent the height (in millimeters) of each student in the class.

输出

For each data set there is one line of output. The single output line consists of the data set number,K, followed by a single space followed by total number of steps taken back.

样例输入

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 17

弧了好久没更新博客..实际上是前几天去考科目二了(险过,丢人)

这道题第一眼就感觉用upper_bound,就算数据水但是还有打的必要的

upper_bound的作用就是寻找比较一个vector大数的位置并且返回,这里找一下然后算一下位置求和就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> shu;
int main(){
scanf("%d",&n);
long long s=0;
int kk[25];
for(int i=1;i<=n;i++){
int num;
s=0;
shu.clear();
scanf("%d",&num);;
for(int j=1;j<=20;j++){
scanf("%d",&kk[j]);
s+=shu.end()-upper_bound(shu.begin(),shu.end(),kk[j]);
shu.insert(upper_bound(shu.begin(),shu.end(),kk[j]),kk[j]);
}
printf("%d %d\n",i,s);
}

return 0;
}