一.石头
题目描述:
沙滩按照线型摆放着n个大小不一的球形石头,已知第i个石头的半径为ri,且不存在两个石头有相同的半径。为了使石头的摆放更加美观,现要求摆放的石头的半径从左往右依次递增。因此,需要对一些石头进行移动,每次操作可以选择一个石头,并把它放在剩下n−1个石头在最左边或最右边。问最少需要操作多少次才能将这n个石头的半径变成升序?
输入描述
第一行一个整数n,表示石头的个数。(1 <= n <= 100000) 第二行n个整数,表示从左往右石头的半径r1,r2,...,rn。(1 <= ri <= n),且保证不存在两个不同的石头拥有相同的半径。
输出描述
最少操作次数
样例输入
5
4 1 2 5 3
样例输出
2
通过了73%
cd = int(input()) cc = list(map(int,input().split())) def lengthOfLIS(nums): ls=sorted(nums) stack=[] res=[] for i in ls: cur=nums.index(i) if not stack: stack.append(cur) else: if cur>stack[-1]: stack.append(cur) else: res.append(len(stack)) stack=[cur] return max(res) print(cd-lengthOfLIS(cc))
二.01交替
题目描述:
给你一个长度为n的01串。现在想让你找出最长的01交替子串(子串可以不连续)比如:1010,0101是01交替的串,1101则不是。现在你可以把某一个连续的区间进行翻转,即0变1,1变0。问修改之后的最大01交替子串的长度是多少。
输入描述
输入第一行包含一个整数n (1 <= n <= 100000) 表示01串的长度。 第二行包含一个01串。
输出描述
输出一个数表示符合题意的子串长度
样例输入
8
10000011
样例输出
5
AC
n = int(input()) arr = input() cnt = 1 for i in range(n-1): if arr[i] != arr[i+1]: cnt += 1 if cnt < n-1: print(cnt+2) else: print(n)