Niuke real problem programming - day13

Programming environment ：c++

1、 Building blocks

describe

Xiao Ming has a bag of rectangular building blocks , If a building block A The length and width of is no larger than another building block B The length and width of , Then the building blocks A It can be built on building blocks B On top of . Curious Xiao Ming especially wants to know how many layers this bag of building blocks can be built at most , Can you help him find a way ？

Define the length of each rectangle L And width W , The number of rectangles in the bag is n .

If there are 5 The building blocks are (2, 2), (2, 4), (3, 3), (2, 5), (4, 5), It is not difficult to judge that these building blocks can be built at most 4 layer , because (2, 2) < (2, 4) < (2, 5) < (4, 5).

Algorithmic thought ：

The title requires that the length and width of the upper layer of building blocks should be smaller than that of the lower layer , Find the longest number of layers . First, we will arrange all rectangular building blocks in ascending order according to the length first , Then traverse to get all the widths after sorting , Get a new array . Because the time required by the topic is relatively limited , So here we choose the dichotomy with the best time complexity to sort , Get a wide ascending priority subsequence , The size of the printout subsequence is the longest number of layers .

The code part implements ：

Two points ,len Is the length of the subsequence

2、 Odd number

describe ：

Small M Suddenly interested in odd numbers . Suppose a number n, If [n/1]+[n/2]+...+[n/k](k Is a positive integer approaching positive infinity ) It's an even number , Then this number is an odd number , Now let's give an interval [a,b], seek [a,b] How many strange numbers are there between .

[x] No greater than x Maximum integer for .

Algorithmic thought ：

    Solve problems with mathematical ideas ： according to 100 It is not difficult to find the odd number data within the enumeration ,, In each line i For even when , In the interval [i2,(i+1)2)] The inner numbers are all odd numbers that meet the requirements . So according to the scope given by the title ab, First, traverse to the smallest i Satisfy i^2>=a, Yes ab Judge the middle number , When i-1 For even when , Add the odd number in the range ; otherwise ,i++ Extend back , until i^2 beyond b Range . After the last judgment , Print out the final result .

 

The code part implements ：

3、 The largest sum of successive subarrays

describe

Enter an array of integers （ There could be positive and negative numbers ）, Find a continuous subarray in an array （ At least one element ） The largest sum of . The required time complexity is O(n).

Algorithmic thought ： Abandon the past and <0 Part of and , Get the sum of the largest subarray after traversal .

Part of the code implementation ：