竹園論壇

標題: d401 - B-成績單 [打印本頁]

作者: Sylveon 時間: 2014-5-6 15:10
標題: d401 - B-成績單
原題：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 時間: 2014-5-6 20:08
好像可以用nth_element

歡迎光臨竹園論壇 (http://forum.tfcis.org/)