데이터 구조 와 알고리즘 실험 문제 10.1 신의 지시 자
알다 시 피 dota 에서 신의 지시 자의 큰 방법 은 모든 데 미 지 를 막 을 수 있 지만 큰 방법 이 끝 날 때 모든 데 미 지 를 한꺼번에 결산 합 니 다.신의 명령 자 는 큰 방법 을 사용 하 는 동안 n 번 의 상 처 를 입 었 다. 그 는 지금 자신 이 입 은 상처 중의 k 번 째 데 미 지 수 치 를 알 고 싶 어 하지만 그 는 생각 할 때 다시 상 처 를 입 을 것 이다. 그 는 이미 정확 한 답 을 알 수 없다.그래서 지금 도움 을 청 하 러 왔 습 니 다.
★ 데이터 입력
첫 줄 에 두 개의 정수 n, m (1 < = n, m < = 50000) 를 입력 하 십시오.두 번 째 줄 은 n 개의 정수 가 있어 서 신의 지시 자 에 게 이미 입 은 상 처 를 준다.다음은 m 번 의 질문 이 있 습 니 다. 매번 물 어 볼 때마다 두 개의 정수 a, k 가 있 습 니 다.a 가 0 일 때 신의 지시 자가 다시 상 처 를 입 었 다 는 것 을 의미 하고 k 는 그 가 받 은 데 미 지 값 이다.a 가 1 이면 신의 지시 자가 그 가 받 은 상처 중의 k (k 가 받 은 데 미 지 횟수 를 초과 하지 않 음) 의 작은 데 미 지 를 알 고 싶다 는 것 을 의미한다.
★ 데이터 출력
a 가 1 이면 k 번 째 데 미 지 를 출력 합 니 다.
예제 입력 5 5 1 3 5 7 9 1 4 0 6 1 4 0 5 1 4
출력 예시
7 6 5
나 는 삽입 할 때 k 도 50000 이내 라 고 생각 했 는데 바로 fenwick 나무 로 해결 했다. 나중에 물 어 보 니 범위 가 Int 인 것 같 아서 나 무 를 나 누 거나 균형 나 무 를 사용 할 수 밖 에 없 었 다.
학생 들 말 로 는 삽입 순서 가 지 났 다 고 하 던 데...............................................나 도 방금 하나 쳤 는데 정말...이 데 이 터 는 얼마나 필요 합 니까?
방법 1: 정렬 삽입
처음에는 nlogn 으로 정렬 을 했 습 니 다.O(nlogn)
매번 삽 입 된 수 를 삽입 합 니 다. 최 악의 경우 전체 배열 (마지막 부터 끝까지) O (m * n) 를 옮 겨 다 닙 니 다.
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100000+10;
int a[MAXN];
int main()
{
int n,m,i;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int cmd,k,len=n;
for(i=0;i<m;i++)
{
scanf("%d%d",&cmd,&k);
if(cmd==1)
printf("%d
",a[k-1]);
else
{
//
int j;
if(len==0)
{
a[0]=k;
len++;
continue;
}
for(j=len;j>=0;j--)
{
if(k < a[j-1])
a[j]=a[j-1];
else
{
a[j]=k;
break;
}
}
len++;
}
}
}
방법 2: 오프라인 + 구분 트 리
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXM=20;
const int MAXN=100000+10;
int data[MAXM][MAXN], num[MAXM][MAXN], sorted[MAXN];
struct node
{
int kind; //kind=0 kind=1
int k;
}p[MAXN];
void Build(int depth, int L, int R) {
if (L == R)
return;
int same, mid, i, left, right;
mid = (L + R) >> 1;
same = mid - L + 1;
left = L;
right = mid + 1;
for (i = L; i <= R; i++) {
if (data[depth][i] < sorted[mid])
same--;
}
//same val_mid , 。
for (i = L; i <= R; i++) {
if (data[depth][i] < sorted[mid])
data[depth + 1][left++] = data[depth][i];
else if (data[depth][i] == sorted[mid] && same) {
data[depth + 1][left++] = data[depth][i];
same--;
} else
data[depth + 1][right++] = data[depth][i];
num[depth][i] = num[depth][L - 1] + left - L;
//num
}
Build(depth + 1, L, mid);
Build(depth + 1, mid + 1, R);
}
int findk(int L, int R, int x, int y, int k,int depth) {
if (L == R)
return data[depth][L];
int mid, left, temp;
mid = (L + R) >> 1;
left = num[depth][y] - num[depth][x - 1];
temp = num[depth][x - 1] - num[depth][L - 1];
if (left >= k)
return findk( L, mid, L + temp, L + temp + left - 1, k,depth + 1);
else {
k -= left;
temp = x - L - temp;
left = y - x + 1 - left;
return findk( mid + 1, R, mid + temp + 1, mid + temp + left, k,depth + 1);
}
}
int main() {
int n,m,i;
int len=0;
scanf("%d%d", &n,&m);
for(i=0;i<n;i++)
{
scanf("%d",&p[i].k);
len++;
sorted[len] = data[0][len] = p[i].k;
p[i].kind=0; //insert
}
int tot=n+m;
for(;i<tot;i++)
{
int action;
scanf("%d%d",&action,&p[i].k);
if(action==0)
{
p[i].kind=0;
len++;
sorted[len] = data[0][len] = p[i].k;
}
else if(action==1)
{
p[i].kind=1;
}
}
sort(sorted + 1, sorted + len + 1);
Build(0, 1, len);
int cnt=0; //
for(i=0;i<tot;i++)
{
if(p[i].kind==0)
cnt++;
else
printf("%d
",findk(1,len,1,cnt,p[i].k,0));
}
return 0;
}
방법 3 대 추가 정보 BST
왼쪽 아들 의 개 수 를 기록 하여 조회 하기 편리 하 다.
조회 할 때 왼쪽 아들 개수 보다 크 면 오른쪽으로 k = k - num - 1 을 조회 합 니 다. 그렇지 않 으 면 왼쪽으로 조회 합 니 다.
#include<cstdio>
struct node
{
node *left;
node *right;
int num;
int cntL;
node(){ left=right=NULL; cntL=0; }
};
struct BST
{
node *root;
BST() {root=NULL;}
void insert(int num)
{
node *p=root,*p_fa=NULL;
node *temp=new node;
temp->num=num;
while(p)
{
p_fa=p;
if(num <= p->num) //left;
{
p->cntL++;
p=p->left;
}
else //right
p=p->right;
}
if(root==NULL)
{
root=temp;
return;
}
if(num <= p_fa->num)
p_fa->left=temp;
else
p_fa->right=temp;
}
int find(int k)
{
node *p=root;
while(k!=p->cntL+1)
{
if(k> p->cntL) //
{
k=k-p->cntL-1;
p=p->right;
}
else
{
p=p->left;
}
}
return p->num;
}
}bst;
int main()
{
int n,m,i;
scanf("%d%d",&n,&m);
int cmd,k;
for(i=0;i<n;i++)
{
scanf("%d",&k);
bst.insert(k);
}
for(i=0;i<m;i++)
{
scanf("%d%d",&cmd,&k);
if(cmd==0)
bst.insert(k);
else
printf("%d
",bst.find(k));
}
return 0;
}
방법 4: SBT
BST 가 극단 적 인 상황 에서 하나의 체인 으로 퇴화 하면 조회 효율 이 O (n) 로 변 한 다 는 것 을 잘 알 고 있 습 니 다.
물론 이 문 제 는 데이터 가 특별 하고 삽입 정렬 이 지 났 으 니 BST 는 말 할 필요 가 없다.
근 데 실제 상황 은 물이 물 인지 아 닌 지 모 르 겠 어 요!
밸 런 스 트 리 는 AVL, 레 드 블랙 트 리, treap, SBT 가 있 습 니 다.
splay 도 사용 할 수 있 지만 느 린 QAQ 입 니 다.
AVL 과 레 드 블랙 트 리 는 쓰기 가 복잡 합 니 다. treap 과 SBT 를 추천 합 니 다.
SBT 를 만 든 작가 의 자랑 에 따 르 면 SBT 가 가장 빠르다. 다음은 SBT 를 소개 한다.
SBT 는 모두 Size Balanced Tree 라 고 부 르 며 밸 런 스 트 리 이기 도 하 다.
그 는 SB 도 BT 도 아니다.
SBT 트 리 에 대한 나의 소개: Size Balanced Tree (SBT 트 리) 정리http://blog.csdn.net/murmured/article/details/17029131
이번 에는 많은 사람들 이 이 걸 로...
#include<cstdio>
const int MAXN=200000+10;
struct SBT
{
int left[MAXN]; //left son
int right[MAXN]; //right son
int size[MAXN]; //the num of sons
int value[MAXN]; //value
int len; //length
int root;
SBT(){ root=len=0; }
void right_rotate(int &t)
{
int k=left[t];
left[t]=right[k];
right[k]=t;
size[k]=size[t];
size[t]=size[ left[t] ] + size[ right[t] ] +1;
t=k;
}
void left_rotate(int &t)
{
int k=right[t];
right[t]=left[k];
left[k]=t;
size[k]=size[t];
size[t]=size[left[t]]+size[right[t]]+1;
t=k;
}
void insert(int &t,int v)
{
if(!t)
{
t=++len;
value[t]=v;
size[t]=1;
left[t]=right[t]=0;
return;
}
size[t]++;
if(v < value[t])
insert(left[t],v);
else
insert(right[t],v);
matain(t);
}
void matain(int &t)
{
if(size[ left[ left[t] ] ] > size[ right[t] ] )
{
right_rotate(t);
matain(right[t]);
matain(t);
}
else if( size[ right[ left[t] ] ]>size[ right[t] ] )
{
left_rotate(left[t]);
right_rotate(t);
matain(left[t]);
matain(right[t]);
matain(t);
}
else if(size[ right[ right[t] ] ]>size[ left[t] ])
{
left_rotate(t);
matain(left[t]);
matain(t);
}
else if(size[ left[ right[t] ] ]>size[ left[t] ])
{
right_rotate(right[t]);
left_rotate(t);
matain(left[t]);
matain(right[t]);
matain(t);
}
}
int select(int t,int k)
{
if(k==size[left[t]]+1)
return value[t];
if(k<=size[left[t]])
return select(left[t],k);
else
return select(right[t],k-size[left[t]]-1);
}
}sbt;
int main()
{
int n,m,i;
scanf("%d%d",&n,&m);
int cmd,k;
for(i=0;i<n;i++)
{
scanf("%d",&k);
sbt.insert(sbt.root,k);
}
for(i=0;i<m;i++)
{
scanf("%d%d",&cmd,&k);
if(cmd==0)
sbt.insert(sbt.root,k);
else
printf("%d
",sbt.select(sbt.root,k));
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.