Niuke real problem programming - Day12

Compile environment ：c++

1、 street lamp

describe ：

One is long l There are n Street lights , If the starting point of this street is 0, The finish for l, The first i The coordinates of street lights are ai , The longest distance that each lamp can cover is d, For lighting needs , All lights must cover the whole street , But in order to save electricity , To make this d Minimum , Please find the smallest d.

Algorithmic thought ：

The topic requires finding the smallest lighting range of street lamps , In fact, it is to sort the input disordered street lamp positions , Find the maximum distance between adjacent street lamps , Boundary also needs to be considered , Take the maximum value and output . Note that the title has multiple groups of inputs and the output retains two decimal places .

The code part implements ：

2、 Xiaoyi's upgrade road

describe

Xiaoyi often indulges in online games . There is a , He's playing a strange upgrade game , His character's initial ability value is a. Over the next period of time , He will meet in turn n A monster , Each monster's defense is b1,b2,b3...bn. If you encounter a monster defense bi Less than or equal to Xiaoyi's current ability value c, Then he can easily defeat the monster , and And increase your ability value bi; If bi Greater than c, Then he can also defeat monsters , But his ability value can only increase bi And c Maximum common divisor of . So here comes the question , After a series of exercises , What is the final ability value of Xiaoyi ?

Algorithmic thought ：

    The title description is very clear , Requirements bi and a Common divisor of ability value or directly defeat , Output the capability value after the final upgrade . The topic has multiple sets of use case input .

The code part implements ：

3、 Pig in the tuyere - China's bull market

describe ：

Under the wind , Pigs can fly . Today's Chinese stock market is a bull market , It can be said. “ Miss waiting seven years ”. Give you a chance to look back on history , A stock is known to be n The price trend of the day , In length n An array of integers representing , No i Elements （prices[i]） Represents the number i Day's share price . Suppose you didn't have stocks at first , But there are at most two purchases 1 Shares then sold 1 The opportunity of stock market , And before you buy, you must make sure that you don't have any stocks . If you give up both trading opportunities , Yield is 0. Design algorithm , Calculate the maximum benefit you can get . Input value range ：2<=n<=100,0<=prices[i]<=100

Algorithmic thought ：

    Use the double pointer thought , Because you can't continue to buy when you have stocks , So we can distinguish the two stock transactions . Traversing from front to back , Go back and forth , Before calculating separately i The maximum return of the stock that can be obtained in days and after n-i Day's biggest gain , Stored in an array , Then there will be n-1 In this case ： front 2 God , after n-2 God ; front 3 God , after n-3 God ... Finally, traverse the result array , Take the maximum value of the sum of the two and print it out . The time complexity of each traversal is n, So the total time complexity is O(n).