PAT 107.Stck(30)

914 ワード

タイトルの住所:http://pat.zju.edu.cn/contests/pat-a-practise/1057
これは浙江大学の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