読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.365 ジェンガソート

問題はこちら
No.365 ジェンガソート - yukicoder

後ろから見て、大きい方から順にN~i+1までは順番に並んでいて、iはそうでないとする。
このとき、iをi+1より左に動かすために最低1回の操作が必要
更にこの直後、1~i-1はiより右にあるので、これらをiより左に動かすため同様に最低各1回の操作が必要
あわせてi回の操作が少なくとも必要と分かる
逆に、i~1の順で各1回操作を行えばこれによりソートが完了することが確かめられるので、i回が答え

int main(){
	int i,t,n,a[100010];
	scanf("%d",&n);
	for(t=0;t<n;t++)scanf("%d",a+t);
	i=n;
	for(t=n-1;t>=0;t--)if(a[t]==i)i--;
	printf("%d",i);
	return 0;
}

逆順で調べるといえば再帰

n;
f(i){~scanf("%d",&i)?f(),n-=n==i:0;}
main(){n=!printf("%d",n,f(scanf("%d",&n)));}

82B