PAT 107.Stck(30)
914 ワード
タイトルの住所:http://pat.zju.edu.cn/contests/pat-a-practise/1057
これは浙江大学の2013年の大学院受験の第二次試験で、数値は30分で、大部分の人は開始していくつかのcaseのタイムアウトの状況が現れて、頻繁なPeekMedian操作の時に並べ替えてから、タイムアウトを招いたかもしれません.
ツリー配列を利用して、セカンダリは普通の二分法で、限定された100 ms以内に結果を得ることができる.ツリー配列の紹介
これは浙江大学の2013年の大学院受験の第二次試験で、数値は30分で、大部分の人は開始していくつかのcaseのタイムアウトの状況が現れて、頻繁なPeekMedian操作の時に並べ替えてから、タイムアウトを招いたかもしれません.
ツリー配列を利用して、セカンダリは普通の二分法で、限定された100 ms以内に結果を得ることができる.ツリー配列の紹介
//#include"stdafx.h"
#include
#include
#include
#include
using namespace std;
const int N=100005;
int c[N];
int lowbit(int i){
return i&(-i);
}
void add(int pos,int value){
while(pos0){
res+=c[pos];
pos-=lowbit(pos);
}
return res;
}
int find(int value){
int l=0,r=N-1,median,res;
while(l