1234 开门人和关门人.cpp

ACM 威士忌部分答案

/*
1234 开门人和关门人
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
#include <iostream>
#include <string>
using namespace std;

struct Node
{
    string time;
    int index;
};

const int Max=101;
char num[Max][20];
Node in[Max],out[Max];

int Sift_Down(int i,int n,Node Heap[])   //下移
{
    bool flag;
    Node temp;

    flag=false;
    if(2*i>n)
        return 0;

    do
    {
        i*=2;
        if(i+1<=n && Heap[i+1].time>Heap[i].time)
            i++;
        if(Heap[i/2].time<Heap[i].time)
        {   temp=Heap[i];Heap[i]=Heap[i/2];Heap[i/2]=temp;}
        else
            flag=false;
    }while(2*i<=n || flag);

    return 1;
}

int Make_Heap(int n,Node Heap[])    //转换为大顶堆
{
    int i;

    for(i=n/2;i>=1;i--)
        Sift_Down(i,n,Heap);

    return n;
}

int HeapSort(int n,Node Heap[])  //非降序排序
{
    int i;
    Node temp;

    Make_Heap(n,Heap);
    for(i=n;i>=2;i--)
    {
        temp=Heap[i];Heap[i]=Heap[1];Heap[1]=temp;
        Sift_Down(1,i-1,Heap);
    }

    return 1;
}

int main()
{
    int t,n,i;
    
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>num[i]>>in[i].time>>out[i].time;
            in[i].index=out[i].index=i;
        }
        if(n==1)
            cout<<num[1]<<' '<<num[1]<<endl;
        else
        {
            HeapSort(n,in);
            Make_Heap(n,out);
            cout<<num[ in[1].index ]<<' '<<num[ out[1].index ]<<endl;
        }

    }
    return 0;
}