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 for 1

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

③⭐⭐ Binary Search Answer#

• 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 depends on the convenience of solving with func, it is not necessary

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 >, with 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 a reference, it can be removed, but const must be added~
  • Must check the length, otherwise 53 is lexicographically larger than 12345
  • 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
  • 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): Calculate the number of segments that can be cut based on mid, length mid is the required answer
• Code
  • 
  • The right boundary needs to be determined, confirmed 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
    • Calculate 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: Cutting Rope (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 search, based on the answer to judge
• Code
  • 
  • Floating point binary search
  • Directly discard numbers after the second decimal point
    • Idea one: *100→convert to int→divide by 100.0→set precision %.2f
    • Idea two: -0.005→set precision %.2f
    • For reference: C++ Rounding: Downward, Upward, Rounding, Directly Truncating-CSDN
      • %.2f, are all rounding mechanisms
      • Convert to int: directly remove the decimal point and the following decimals

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 should be placed carefully; if unsure, use it everywhere
• 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
  • 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, corresponds to 0
    • Answer (sum of segments) mid large → judging basis (number of segments) s few, meets the condition, corresponds to 1
    • Since we are looking for the minimum maximum sum, consider the boundary
    • ❓❗ If looking for the maximum maximum sum, it would change to 111110000 situation
  • 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 minimum jump distance
  • The starting point and endpoint are implicitly present: min(D(i+1) - Di) → L (distance from start to end)
  • 111110000
    • Since we are looking for the maximum value, the further right the value is larger, so find the last 1
• Code
  • 
  • Remember to store starting and ending points!
  • Consider traversing to the end stone but not moving the end 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 above 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 above sequence segmentation!
    • Second step: The start and end numbers for each person copying are 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's sort?-Zhihu
  • For int, string: can directly compare sizes, default sorting from smallest to largest
  • For custom structures
    • Overload the less than operator
    • Write your own sorting method cmp

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

Points to Consider#

Tips#

Course Notes#