ural 1100 Final Standings

1100. Final Standings

Time Limit: 1.0 second
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 N lines contains two integers 1 ≤ ID ≤ 10⁷ 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 using bubble sort (or analog).

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

Hint

Bubble sort works following way:
while (exists A[i] and A[i+1] such as A[i] < A[i+1]) do
   Swap(A[i], A[i+1]);

Problem Author: Pavel Atnashev
Problem Source: Tetrahedron Team Contest May 2001

题目描述：

一道排序题目，就是要对一个结构体进行排序；但有一点特殊的要求就是要保证相同的m的数据，要保证原来的顺序，这样使用单纯的快排就会卡在第四组数据上；

那么我们如何处理？

使用bubble sort当然可以。这是显然的，但是时间上是会卡的；

那么肿么办？

改进快排，在结构体中添加一项order表示数据在原来所在的位置，当m相同时就按照order进行排序；

那么这样处理之后就可以了，经我测试ac。

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
    int id;
    int key;
    int n;
}stu[150050];
/*
void swap(int i,int j)
{
    int tempid=stu[i].id;
    int tempn=stu[i].n;
    stu[i].id=stu[j].id;
    stu[i].n=stu[j].n;
    stu[j].id=tempid;
    stu[j].n=tempn;
}*/
bool cmp(node a,node b)
{
    if(a.n==b.n)
        return a.key<b.key;
    else
    {
        return a.n>b.n;
    }
}
int main()
{
    int k;
    scanf("%d",&k);
    int i,j;
    for(i=0;i<k;i++)
    {
        scanf("%d%d",&stu[i].id,&stu[i].n);
        stu[i].key=i;
    }
    sort(stu,stu+k,cmp);
    /*
    for(i=0;i<k-1;i++)
    {
        for(j=i+1;j<k;j++)
        {
            if(stu[i].n<stu[j].n)
            {
                swap(i,j);
            }
        }
    }*/
    for(i=0;i<k;i++)
    {
        printf("%d %d\n",stu[i].id,stu[i].n);
    }
    //system("pause");
    return 0;
    
}

 很短很easy~

但是如果仅仅是这样那么这道题目就是一道纯水题。写出来也没有什么意思，那么当你看m时你会发现，-1<m<101的！

这很关键，看到这里有想法了吗？

笔者想到了序数排序；以m为序数，按原来书序插入即可！

代码如下：

#include <iostream>
using namespace std;
struct node
{
    int id;
    int m;
    node* next;
}stu[150050];
struct list
{
    node* head;
    node* next;
}L[110];
void Init()
{
    int i;
    for(i=0;i<110;i++)
    {
        L[i].head=NULL;
        L[i].next=NULL;
    }
}       
int main()
{
    int n;
    cin>>n;
    int i,j;
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&stu[i].id,&stu[i].m);
        if(L[stu[i].m].head==NULL)
        {
            L[stu[i].m].head=&stu[i];
            L[stu[i].m].next=L[stu[i].m].head;
            stu[i].next=NULL;
        }
        else
        {
            L[stu[i].m].next->next=&stu[i];
            L[stu[i].m].next=&stu[i];
            stu[i].next=NULL;
        }   
    }
    for(i=100;i>=0;i--)
    {
        if(L[i].head)
        {
            node* p=L[i].head;
            while(p)
            {
                printf("%d %d\n",p->id,p->m);
                p=p->next;
            }
        }
    }
    //system("pause");
    return 0;
}
 

这样下来时间比快排还少一些；但是由于使用了很多指针，内存消耗打了很多；

 

还可以使用桶排序：笔者没有写和上面的想法基本是一致的；

短小精悍：

    program URAL_1100;  
    var  
      id:array[1..150000] of longint;  
      score:array[1..150000] of shortint;  
      i,k,n:longint;  
    begin  
      readln(n);  
      for i:=1 to n do  
        readln(id[i],score[i]);  
      for k:=100 downto 0 do  
        for i:=1 to n do  
          if score[i]=k then  
            writeln(id[i],' ',k);  
    end.  

 这样的一道题目，其实很简单但是极为经典。

你想到了几种呢？