Niuke real problem programming - Day11

Compile environment ：c++

1、 Cut grid paper

describe

Dudu bear has a piece of grid paper , But there are some dots on the paper , Every point is on the grid , If the grid is regarded as a coordinate system whose coordinate axis is parallel to the grid line , Each point can use a pair of integers x,y To express . Dudu bear must draw a square along the grid line , Make all points on the inside or boundary of the square . Then cut out this square . Ask the minimum area of the cut square .

Algorithmic thought ：

If the topic wants to meet all the points , Cutting of minimum area , In fact, it is to ask for x Direction and y The maximum length in the direction , Then take the large value as the side length of the square to get the smallest square .

The code part implements ：

2、 code

describe ：

Suppose that the coding range of a code is a ~ y Of 25 Letters , from 1 A to 4 Bit code , If we sort the codes in dictionary order , Form an array as follows ： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy among a Of Index by 0,aa Of Index by 1,aaa Of Index by 2, And so on . Write a function , The input is any code , Output the corresponding Index.

Algorithmic thought ：

    Find the corresponding rule according to the requirements of the topic, which is the multiple relationship between each bit and a Location distance , Examples are analyzed regularly ： General ：temp=temp*25+(str[i]-'a'), The relationship between each person . If it is 4 Bit is 4 layer temp Of value and . Be careful when rounding ＋1, such as 4 Bit code , that 1、2、3 Bit time required +1.

The code part implements ：

 3、 Pay a bonus

describe ：

 Fox held a hacker marathon , The whole company is divided into N A set of , Each group has a room in a row to start the competition , The results were not announced after the game , But each group can see the score of the group with lower score in the two adjacent groups , Bonus will be given after the game , With 1w In units of , Each group will send at least 1w Bonus of , in addition , If a group finds that its bonus is not higher than that of the group with lower grades , Will not be satisfied , As the organizer of the competition , Calculate the minimum amount of bonus needed to satisfy all groups according to the results .

Algorithmic thought ：

  Traverse all groups , Every time 1w Bonus of the unit , If the current group scores higher than the previous group , Then pay the previous group of bonuses +1; Otherwise, the score of the current group is lower than that of the previous group , Then you need to traverse all the groups that have been sent before , Bonus for each group +1, Until the current group is greater than or equal to the previous group , Continue to traverse the Group . After traversal , Add up the bonus of each group and print it out .

The code part implements ：