d401 - B-成績單

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=d401
AC：http://zerojudge.tw/Submissions?problemid=d401&account=lfs92002

找第K大數，用類似快速排序法可以達到理想Θ(N)的時間找第K大。

密技：C++ STL - partial_sort 可以只排序到前K項完成，但在此題可能不太適合使用。


/**********************************************************************************/
/*  Problem: d401 "B-成績單" from 板橋高中98-2模擬測驗                 */
/*  Language: CPP (811 Bytes)                                                     */
/*  Result: AC(0.3s, 4.1MB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2013-05-19 21:09:42                                       */
/**********************************************************************************/


#include<cstdio>
#include<algorithm>
using namespace std;

int search(int *arr,int L,int R,int k)
{
    int p=L,rl=L+1,rr=R;
        while(rl<=rr)
        {
                while(rl<=rr && arr[rl]<=arr[p] )++rl;
                while(rl<=rr && arr[p] < arr[rr])--rr;
                if(rl<rr)swap(arr[rl],arr[rr]);
        }
        swap(arr[p],arr[rr]);
        if(rr==k)return arr[rr];
        if(rr> k)return search(arr,L,rr-1,k);
        return search(arr,rr+1,R,k);
}
int Arr[1000000],Brr[1000000];
int main()
{
        int N,An,Bn,u,v,k,ak,bk;
        while(~scanf("%d",&N))
        {
                An=Bn=0;
                while(N--)
                {
                        scanf("%d%d",&u,&v);
                        if(u==1)
                        {
                                Arr[++An]=-v;
                        }
                        else
                        {
                                Brr[++Bn]=-v;
                        }
                }
                scanf("%d",&k);
                ak=search(Arr,0,An,k);
                bk=search(Brr,0,Bn,k);
                if(ak<bk)
                        printf("1 %d\n",bk-ak);
                else
                        printf("2 %d\n",ak-bk);
        }
        return 0;
}

allenwhale

好像可以用nth_element