ural 1100. Final Standings（数据结构）
1100. Final Standings
Time limit: 1.0 second
Memory limit: 16 MB
Memory limit: 16 MB
Old contest software uses bubble sort for generating final standings. But now, there are too many teams and that software works too slow. You are asked to write a program, which generates exactly the same final standings as old software, but fast.
Input
The first line of input contains only integer 1 < N ≤ 150000 — number of teams. Each of the next Nlines contains two integers 1 ≤ ID ≤ 107 and 0 ≤ M ≤ 100. ID — unique number of team, M — number of solved problems.
Output
Output should contain N lines with two integers ID and M on each. Lines should be sorted by M in descending order as produced by bubble sort (see below).
Sample
| input | output |
|---|---|
8 1 2 16 3 11 2 20 3 3 5 26 4 7 1 22 4 |
3 5 26 4 22 4 16 3 20 3 1 2 11 2 7 1 |
题意很简单。。。。
原以为用sort排个序即可。。。
wrong了后才发现，在value相等的情况下，不能对元素进行交换。。而sort（用的是快排，是不稳定的排序方式，因而会打乱顺序）
那要怎么办呢？
问了学长才知道有个叫做stable_value的东西～～
所谓stable_sort，是指对一个序列进行排序之后，如果两个元素的值相等，则原来乱序时在前面的元素现在（排好序之后）仍然排在前面。STL中提供stable_sort()函数来让我们进行稳定排序。为了更好的说明稳定排序的效果，我们定义了一个结构体元素，一个value成员和一个index成员，前者表示元素的值，后者表示乱序时的索引。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 5 using namespace std; 6 struct node 7 { 8 long id; 9 int m; 10 bool operator<(const node&temp) const 11 { 12 return m>temp.m; 13 } 14 }kiss[150000+5]; 15 16 17 int main() 18 { 19 // freopen("input.txt","r",stdin); 20 int n; 21 while(cin>>n){ 22 for(int i=0;i<n;i++){ 23 scanf("%ld%d",&kiss[i].id,&kiss[i].m); 24 } 25 stable_sort(kiss,kiss+n); 26 for(int i=0;i<n;i++){ 27 printf("%ld %d ",kiss[i].id,kiss[i].m); 28 } 29 } 30 return 0; 31 }