python/C++课程/待整理知识/啊哈算法/p55.cpp

/*
<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>еĴ<EFBFBD><EFBFBD><EFBFBD>:
https://blog.csdn.net/weixin_40804043/article/details/86501166

<EFBFBD><EFBFBD><EFBFBD><EFBFBD>˼·<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ƿ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݴ<EFBFBD><EFBFBD>ڴ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ľڵ㣬<EFBFBD><EFBFBD>data[right[t]]>data[len]
<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><EFBFBD>ˣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>޸<EFBFBD>rightָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>rightָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӡ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ
*/
#include <stdio.h>
int data[101];
int right[101];//ÿ<><C3BF><EFBFBD>ڵ㶼<DAB5><E3B6BC>һ<EFBFBD><D2BB>ָ<EFBFBD><D6B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>鳤<EFBFBD><E9B3A4>Ҫ<EFBFBD><D2AA>data<74><61><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD>
int main() {
	/*nΪ<6E>û<EFBFBD><C3BB>״<EFBFBD>¼<EFBFBD><C2BC><EFBFBD>Ľڵ<C4BD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڿ<EFBFBD><DABF>Ƴ<EFBFBD>ʼ<EFBFBD><CABC><EFBFBD>ڵ<EFBFBD>ʱ<EFBFBD><CAB1>ѭ<EFBFBD><D1AD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
	lenΪ<EFBFBD><EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>data[0]<EFBFBD><EFBFBD>right[0]<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>±<EFBFBD>1<EFBFBD><EFBFBD>ʼ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>data[len]<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD>Ԫ<EFBFBD><EFBFBD>
	*/
	
	int n,i,len,t;
	int flag = 1;
	scanf("%d",&n);
	//<2F><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>data
	for(i = 1; i<=n; i++) {
		scanf("%d",&data[i]);
	}
	len = n;
	//<2F><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>right
	for(i = 0; i<=n; i++) {
		if(i!=n) {
			right[i] = i+1;
		} else {
			right[i] = 0;
			//<2F><>0<EFBFBD><30>ʾû<CABE><C3BB><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>Ԫ<EFBFBD><D4AA>
		}
	}
	//<2F><>data<74><61>ĩβ<C4A9><CEB2><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD>
	len++;
	scanf("%d",&data[len]);
	/*
	ͨ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD><EFBFBD>򣬵<EFBFBD><EFBFBD>ҵ<EFBFBD>ij<EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ<EFBFBD><EFBFBD><EFBFBD>ڲ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ľڵ<EFBFBD>data[len]ʱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>
	ֱ<EFBFBD><EFBFBD>ָ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊֹ
	*/
	t = 1; //<2F>Բ<EFBFBD><D4B2><EFBFBD><EFBFBD>ڵ<EFBFBD>С<EFBFBD>ڵ<EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>⴦<EFBFBD><E2B4A6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>if..else<73><65><EFBFBD>dz<EFBFBD><C7B3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѭ<EFBFBD><D1AD><EFBFBD><EFBFBD>Ŀ<EFBFBD>ģ<EFBFBD>
	if(data[len]<data[1]) {
		right[0] = len;
		right[len] = 1;
	} else {
		while(t!=0) {
			if(data[right[t]]>data[len]) {
				flag = 0;
				right[len] = right[t];
				right[t] = len;
				break;
			}
			t = right[t];
		}
		//<2F><><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
		if(flag == 1) {
			right[len] = 0; /*<2A><><EFBFBD><EFBFBD>ֻ<EFBFBD><D6BB><EFBFBD>򵥴<EFBFBD><F2B5A5B4><EFBFBD><EFBFBD><EFBFBD>Ҳ<EFBFBD><D2B2><EFBFBD>Բ<EFBFBD><D4B2><EFBFBD>right[t]==0<>Ľڵ<C4BD><DAB5>޸<EFBFBD><DEB8><EFBFBD>ָ<EFBFBD><D6B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
       		 ֻ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѭ<EFBFBD><EFBFBD><EFBFBD>м<EFBFBD><EFBFBD><EFBFBD>if(right[t]==0){temp = t;}
       		 <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ٸij<EFBFBD>right[temp] = len;
        	*/
			right[len-1] = len;
		}
	} //tΪright[0]ͷ<>ڵ<EFBFBD>ָ<EFBFBD><D6B8><EFBFBD><EFBFBD><EFBFBD>׽ڵ<D7BD><DAB5><EFBFBD><EFBFBD>±<EFBFBD>
	t = right[0];
	while(t!=0) {
		printf("%d ",data[t]);
		t = right[t];
	}
	//<2F>ȴ<EFBFBD><C8B4>û<EFBFBD><C3BB><EFBFBD><EFBFBD><EFBFBD>¼<EFBFBD>룬<EFBFBD><EBA3AC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͣ<EFBFBD><CDA3><EFBFBD><EFBFBD>Ŀ<EFBFBD><C4BF>
	getchar();
	getchar();
	return 0;
}