Bo2SS

Simple algorithms also have a complex side~

Binary Search#

① Naive Binary Search#

• Find an exact corresponding value

• The floating point case also holds for ② and ③

②⭐ Special Binary Search#

• Find the boundary between 0 and 1 where 1 occurs

• C++ actually has functions that implement this functionality
  • lower_bound, upper_bound
  • Reference Common Usage of lower_bound() and upper_bound()-CSDN

③⭐⭐ Binary Search for Answers#

• Special Binary Search + func(answer)
  • The value func(answer) used to judge the update condition is obtained based on the answer
  • The value used to judge the update condition generally implies an ordered condition
    • Therefore, whether to sort is related to the convenience of solving with func, not a necessity

HZOJ-380: Leader Voting (sort)#

Sample Input

3
123456799
123456789132456789123456789
11111111111111

Sample Output

2
123456789132456789123456789

• Idea
  • The number of votes is large, so it should be read in as a string, using the string class
    • The string class overloads > and has built-in lexicographical comparison
  • Use struct class, combined with corresponding numbers
  • Use sort
    • First compare lengths, strlen
    • If lengths are the same, use lexicographical order
• Code
  • 
  • const node &a's & is passed by reference, it can be removed, but const must be added~
  • Must check length, otherwise 53 is greater than 12345 in lexicographical order
  • Index starts from 1, otherwise introduces (0, 0)

HZOJ-381: Who Received the Most Scholarships (sort)#

Sample Input

4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1

Sample Output

ChenRuiyi
9000
28700

• Idea

  • When the bonuses are tied for first, output the one that appeared first
    • So you need to record the number, sort is unstable
  • Just pay attention to the details of the bonus calculation rules

• Code

• 

HZOJ-386: Onlookers (①)#

Sample Input

5 3
1 3 26 7 15
26 99 3

Sample Output

3
0
2

• Idea
  • Sorting + naive binary search
  • The number and index of the melons need to be combined into a struct
• Code
  • 
  • Mid calculation formula to prevent overflow
    • = ((long long)l + r) / 2
    • = l + (r - l) / 2
  • If not found, output 0, f initialized to 0

HZOJ-387: Upgraded Onlookers (②)#

Sample Input

5 5
1 3 26 7 15
27 10 3 4 2

Sample Output

0
5
2
4
2

• Idea
  • Abstracted as a bunch of 0s and a bunch of 1s, find the first occurrence of 1
  • Consider the case of outputting 0
• Code
  • 
  • There are two ways to handle the output of 0
  • 000000011111111

Leetcode-278: First Bad Version (②)#

Example

Given n = 5, and version = 4 is the first bad version.
Call isBadVersion(3) -> false
Call isBadVersion(5) -> true
Call isBadVersion(4) -> true
So, 4 is the first bad version. 

• Idea
  • Use special binary search to do
  • 000000011111111
• Code

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;  // Version numbers start from 1
        while (l != r) {
            int mid = ((long long)l + r) / 2;  // Prevent overflow method one
            // int mid = l + (r - l) / 2;  // Prevent overflow method two
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

HZOJ-390: Log Cutting (③)#

Sample Input

3 8
6
15
22

Sample Output

5

• Idea
  • Left boundary → Right boundary: 1 → max(Xi)
  • 111111110000000
  • ③ = ② + func(mid)
    • func(mid): Determine how many segments can be cut based on mid, length mid is the required answer
• Code
  • 
  • The right boundary needs to be determined during input

HZOJ-389: Irritable Programmer (③)#

Sample Input

5 3
1
2
8
4
9

Sample Output

3

• Idea
  • Upper and lower bounds of distance: 1 → max(Xi)
    • For simplicity, directly take 1 and the largest workstation number
    • If you want to be precise, you can take the difference between the smallest and largest workstation numbers
  • Answer → Judging basis: distance → number of people that can be arranged
  • 111111100000
• Code
  • 
  • Sorting is necessary to calculate the number of people that can be arranged based on distance
  • func()
    • Need to record the position of the last arranged person last
    • Determine the number of people that can be arranged s
    • Initialization: the number of people that can be arranged s is 1, the position of the last arranged person last is num[0]

HZOJ-393: Rope Cutting (Decimal ③)#

Sample Input

4 11
8.02
7.43
4.57
5.39

Sample Output

2.00

• Idea
  • Similar to log cutting, but the data is floating point
    • Conditions and update formulas are different
  • Determine the left and right boundaries for searching, based on the answer to judge the basis
• Code
  • 
  • Floating point binary search
  • Directly discard the numbers after the decimal point by 2
    • Idea one: *100→convert to int→divide by 100.0→set precision %.2f
    • Idea two: -0.005→set precision %.2f
    • For reference: C++ Rounding: Floor, Ceiling, Round, Directly Truncate-CSDN
      • %.2f, are both rounding mechanisms
      • Convert to int: directly remove the decimal point and the following decimals to round

HZOJ-82: Logging#

Sample Input

4 9
20 17 15 10

Sample Output

14

• Idea
  • Similar to log cutting, but the judging basis is whether the cut wood meets the required wood length
  • Upper and lower bounds: 0 → max()
  • Note that the data range is large, and addition may overflow, so use long long
    • long long needs to be thought out, if not, can use it all
• Code
  • 
  • Think clearly about the relationship between the answer and the judging basis

HZOJ-391: Sequence Segmentation#

Sample Input

5 3
4
2
4
5
1

Sample Output

6

• Idea
  • The minimum maximum sum
  • 0000000111111, find the first 1
    • Answer (sum of segments) mid small → judging basis (number of segments) s many, does not meet the condition, corresponding 0
    • Answer (sum of segments) mid large → judging basis (number of segments) s few, meets the condition, corresponding 1
    • Since we are looking for the minimum maximum sum, consider the boundary
    • ❓❗ If looking for the maximum maximum sum, it would change to the situation of 111110000
  • Left and right boundaries: max(Ai) → sum(Ai)
• Code
  • 
  • 
  • ⭐ Think carefully about the func function!
  • Pay attention to long long type

HZOJ-394: Jumping Stones#

Sample Input

25 5 2 
2
11
14
17 
21

Sample Output

4

• Idea
  • The maximum value of the shortest jump distance
  • The starting point and endpoint are implicitly present: min(D(i+1) - Di) → L (the distance from the starting point to the endpoint)
  • 111110000
    • Since we are looking for the maximum value, the further right the value is, the larger it is, so find the last 1
• Code
  • 
  • Remember to store the starting point and endpoint!
  • Consider the thought of traversing to the endpoint stone but not moving the endpoint stone
    • Can equivalently use moving the previous stone

HZOJ-392: Throwing Bottle Caps#

Sample Input

5 3
1
2
3
4
5

Sample Output

2

• Idea
  • Exactly the same as the aforementioned irritable programmer!
• Code

HZOJ-395: Copying Manuscripts#

Sample Input

9 3
1 2 3 4 5 6 7 8 9

Sample Output

1 5
6 7
8 9

• Idea
  • Everyone's copying speed is the same, the numbers correspond to time
  • Must be continuous, the book cannot be split
  • Steps
    • First step: Find the maximum value, exactly the same as the aforementioned sequence segmentation!
    • Second step: Each person's start and end number of copying, stored in an array
      • After obtaining the maximum value, scan the sequence from back to front
        • If there are multiple solutions, let the earlier person copy less
      • Slightly troublesome, tests coding skills
• Code

Additional Knowledge Points#

• The struct in C++ is a class
  • Member access permissions are private by default, while struct is public by default
• sort usage

int num[105];
sort(num, num + n, cmp); 

• • num: starting address of the interval to be sorted; num + n: address of the next address of the end of the interval; cmp:
  • ⭐ By default, it is unstable
    • The underlying uses quicksort, combined with insertion sort and heapsort
    • Reference A Deep Pit Interview Question in C++: What Sorting Algorithm is Used in STL Sort?-Zhihu
  • For int, string: can directly compare sizes, default from small to large sorting
  • For custom structures
    • Overload the less than sign
    • Write your own sorting method cmp

bool cmp(node a, node b) {
  return a.x > b.x;  // Sort according to x in node from large to small
}

Points to Consider#

Tips#

Course Notes#