# Q1: The problem of dividing oranges

## Problem Description

There are n students in the class lined up in a row from front to back, and the grades of these students have been known, and the grade of the i-th student is ai. The head teacher wants to assess the number of oranges given by the students based on their previous grades. In order to motivate outstanding students, the following requirements need to be met when giving out oranges;

- There must be more oranges for students with good grades in neighboring students. If adjacent students have the same grades, they must be assigned an equal number.
- Each student is assigned at least one orange

Due to budget constraints, the homeroom teacher wanted to give out as few oranges as possible. , at least how many oranges do you need to prepare?

### input format

The first line is an integer n, representing the number of students.

The next line contains n integers, the ith integer a, which represents the grade of the ith student,

### output format

Output the answer, that is, how many oranges need to be prepared at least.

### Input and output example

enter

5

3 4 5 4 3

output

9

### Example 1 Explanation

The number of oranges each student gets is 1, 2, 3, 2.1, so at least 9 oranges need to be prepared

Data scale and conventions

Guarantee 1<n≤10^6,0<ai<10.

## ideas

initial array list

list | 3 | 4 | 5 | 4 | 3 |
---|---|---|---|---|---|

nums | 1 | 1 | 1 | 1 | 1 |

The first step is to fill

list | 20 | 3 | 4 | 5 | 4 | 3 | 20 |
---|---|---|---|---|---|---|---|

nums | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

while loop, when the score is higher than the student on the left, and there are no more oranges than the classmate on the left, or higher than the classmate on the right, but there are no more oranges than the classmate on the right, give him an orange and continue the loop

first round:

list | 20 | 3 | 4 | 5 | 4 | 3 | 20 |
---|---|---|---|---|---|---|---|

nums | 1 | 1 | 2 | 1 | 1 | 1 | 1 |

second round:

list | 20 | 3 | 4 | 5 | 4 | 3 | 20 |
---|---|---|---|---|---|---|---|

nums | 1 | 1 | 2 | 2 | 1 | 1 | 1 |

Third round:

list | 20 | 3 | 4 | 5 | 4 | 3 | 20 |
---|---|---|---|---|---|---|---|

nums | 1 | 1 | 2 | 3 | 1 | 1 | 1 |

Fourth round:

list | 20 | 3 | 4 | 5 | 4 | 3 | 20 |
---|---|---|---|---|---|---|---|

nums | 1 | 1 | 2 | 3 | 2 | 1 | 1 |

End of traversal, return sum(list)-2

## code

n = int(input()) l = list(map(int,input().split())) l.insert(0,20) l.insert(n+1,20) nums = [1 for _ in range(n+2)] index = 1 while index <= n: if (l[index] > l[index-1] and nums[index]<=nums[index-1]) or (l[index]>l[index+1]and nums[index]<=nums[index+1]): nums[index] += 1 index = 1 index += 1 print(sum(nums)-2)

## analyze

Time complexity O(n²), space complexity O(n)

# Q2: From what day will no more trees die?

## Problem Description

There are some trees in a garden, and each tree has been treated with insecticides and sprayed with different amounts of insecticides.

At the end of each day, a tree will die if it has higher levels of pesticides than the tree to its left.

You will be told the initial level of pesticides for each tree. Calculate the number of days after which no more plants will die.

## example

p=[3,6,2,7,5]

On the first and second days, the 1st and 3rd trees die, and the remaining trees are p = [3,2,5]. On day 2, the 3rd tree also dies, and the remaining tree is p=[3,2].

Now no tree has more pesticides than the tree to its left, so the result is day 2.

### enter

A one-dimensional array of integers:

N

int p[n]

### output

No more trees will die from the first few days

## ideas

list | 3 | 6 | 2 | 7 | 5 |
---|

Step 1: Fill the left max(list)+1

list | 8 | 3 | 6 | 2 | 7 | 5 |
---|

Step 2: Traverse the list to find the tree larger than the left, pay attention to update the length of the list

first round

list | 8 | 3 | 2 | 5 |
---|

second round

list | 8 | 3 | 2 |
---|

third round

Since no tree has been killed at this time, exit the loop, day = 2

## code

l = list(map(int,input().split())) # filling l.insert(0,max(l)+1) l.insert(len(l),max(l)+1) day = 1 while True: index = 1 n = len(l)-2 sign = False while index <= n: if l[index]>l[index-1]: sign = True l.pop(index) n = len(l)-2 index += 1 if not sign: break day += 1 print(day-1)

# Q3: Linked list interval flip

## Problem Description

Reverse the interval between the m position and the n position of a linked list whose number of nodes is size, which requires time complexity O(n)

E.g:

The given linked list is 1→2→3→4→5→NULL,m=2,n=4 returns 1→4→3→2→5→NULL.

Data range: the length of the linked list is 0<size<1000, O<mnssize, the value of each node in the linked list meets the requirements of |val |<1000: time complexity O(n)

Example 1

enter:

{1,2,3,4,5},2,4

output:

{1,4,3,2,5}

Example 2

enter:

{5},1,1

output:

{5}

## ideas

When I did it, I felt that it was a bit troublesome to compile a linked list, so I made a list flip.

## code

s = input() s = s.replace("{","") s = s.replace("}","") l = s.split(",") start = int(l[len(l)-2])-1 end = int(l[len(l)-1])-1 for i in range(start, (start + end - 1) // 2 + 1): tmp = l[i] l[i] = l[start + end - i] l[start + end - i] = tmp print("{",end='') print(l[0],end='') for ss in l[1:len(l)-2]: print(",",end='') print(ss,end='') print("}")

# Q4: Version comparison

## Problem Description

The problem is relatively simple, that is, the two version numbers are relatively large.

enter:

"1.0.1","1.0.11"

output:

-1

enter:

"1.0.012","1.0.12"

output:

0

enter:

"2.1.0","1.12.1"

output:

1

## ideas

Convert the input into a list of ints, write down and compare them one by one

## code

def fun(l1,l2): min_len = min(len(l1),len(l2)) for i in range(min_len): if int(l1[i]) > int(l2[i]): return 1 elif int(l1[i]) < int(l2[i]): return -1 if len(l1) > len(l2): return 1 elif len(l1) < len(l2): return -1 else: return 0 s1,s2 = input().split(",") s1 = s1[1:-1] s2 = s2[1:-1] l1 = s1.split(".") l2 = s2.split(".") print(fun(l1,l2))