本文共 888 字,大约阅读时间需要 2 分钟。
有n个杀手排成一行,每个杀手都有一个不同的编号(编号为1-n),在每个夜晚,杀手都会行动,如果某个杀手编号大于他右边的杀手的编号,他就会杀死他右边的杀手,杀手是的行动是瞬间的,因此一个人可能某一个夜晚既杀死了别人又被别人杀死,例如3,2,1这个顺序,在第一个夜晚2会杀死1,同时3也会杀死2。
显而易见,一段时间之后,就不会有人杀或被杀,平安夜也就到来了,请问在平安夜之前有多少个夜晚。
输入第一行是一个整数n(1≤n≤100000),表示杀手的数量。
接下来一行有n个数,是一个1-n的全排列。
输出包含一个整数,表示平安夜之前经历了多少个夜晚。
10
10 9 7 8 6 5 3 4 2 1
2
6
1 2 3 4 5 6
0
在每个夜晚,杀手都会行动,如果某个杀手编号大于他右边的杀手的编号,他就会杀死他右边的杀手。
这说明如果n个数不是从小到大排序的,那么就会有人死亡。
所以不断地从右向左遍历这n个数,如果右边的数小于左边的数,那么删掉右边的数,直到这些数的顺序是从小到大排列的为止。
每次遍历完,都记录此时还剩下的个数,直到此时的个数与上次遍历完的个数相同,就停止遍历,已经满足条件,然后输出共遍历了多少次即可。
import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); Listlist=new ArrayList (); for(int i=0;i 1) { for(int i=list.size()-1;i>=1;i--) { if(list.get(i)
转载地址:http://vszci.baihongyu.com/