寒假第二讲:“二分”

一.二分查找

1.对应思路

这个问题的要求是通过二分查找，在一个已经按升序排列的整数序列中查找是否包含查询的整数。对于每次查询，若该整数在序列中出现，则输出 “Yes”，否则输出 “No”。

输入处理：
- 输入一个整数 nnn，表示数组的大小。
- 接下来输入 nnn 个整数，这些整数已排序。
- 接着输入一个整数 qqq，表示查询次数。
- 对于每次查询，输入一个整数 mmm，需要判断 mmm 是否出现在排序数组中。
二分查找：
- 二分查找是一种高效的查找方法，在一个已排序的数组中查找某个元素的时间复杂度为 O(log⁡n)O(\log n)O(logn)。
- 使用标准库的 lower_bound 函数来实现二分查找。它会返回一个指向数组中第一个大于或等于查询值的迭代器。如果迭代器指向的元素与查询值相同，则表示该元素存在。
输出：
- 如果查询值在数组中存在，则输出 “Yes”；否则输出 “No”。

#include <iostream>
#include <vector>
#include <algorithm>  // For lower_bound
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    int q;
    cin >> q;
    
    for (int i = 0; i < q; ++i) {
        int m;
        cin >> m;
      
        auto it = lower_bound(arr.begin(), arr.end(), m);
  
        if (it != arr.end() && *it == m) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    
    return 0;
}

3.学习总结

该问题要求在已排序的数组中进行多个查找操作，最直观的做法是使用二分查找。二分查找能够将查找时间从 O(n)O(n)O(n) 降低到 O(log⁡n)O(\log n)O(logn)，因此对于大规模数据，能够显著提高效率。利用 C++ STL 提供的 lower_bound 函数，可以高效地实现二分查找，避免手动实现查找算法。通过这种方法，每次查询的时间复杂度为 O(log⁡n)O(\log n)O(logn)，因此总的时间复杂度为 O(qlog⁡n)O(q \log n)O(qlogn)，适合处理较大规模的输入数据。

这个解法对于最大值 n=100000n = 100000n=100000 和 q=100000q = 100000q=100000 的情况也是可行的，满足时间限制。

二.A-B数对

1.对应思路

给定数列以及常数 CCC，要求计算满足条件 A−B=CA - B = CA−B=C 的数对个数。这个问题要求判断在数列中，存在多少对 (A,B)(A, B)(A,B)，使得 A−B=CA - B = CA−B=C，即 A=B+CA = B + CA=B+C。

解决思路：

数学转换：
- 给定条件 A−B=CA - B = CA−B=C，可转化为 A=B+CA = B + CA=B+C。因此，对于每个 BBB，我们只需要判断 B+CB + CB+C 是否出现在数列中。
使用哈希表：
- 使用哈希表（unordered_map）来记录数列中每个数字的出现次数。遍历数列，对于每个数 BBB，计算 B+CB + CB+C，然后检查哈希表中是否有这个数。如果有，则计数增加。
效率问题：
- 用哈希表统计数列中各个数字的出现次数，查找某个数是否存在的操作是 O(1)O(1)O(1)，所以该算法的时间复杂度是 O(N)O(N)O(N)，适用于大规模数据。

2.代码

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    int N, C;
    cin >> N >> C;
    
    vector<int> arr(N);
    unordered_map<int, int> freq;  

    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
        ++freq[arr[i]];
    }
    
    long long count = 0; 

    for (int i = 0; i < N; ++i) {
        int B = arr[i];
        int A = B + C;  // 计算A = B + C
       
        if (freq.find(A) != freq.end()) {
            count += freq[A];  
        }
    }
    
    cout << count << endl;  
    return 0;
}

3.学习总结

哈希表：哈希表在处理需要快速查找的场景中非常有用。在本题中，哈希表帮助我们在 O(1)O(1)O(1) 的时间复杂度内查找某个元素是否存在，使得整体复杂度从 O(N2)O(N^2)O(N2) 降低到 O(N)O(N)O(N)。

优化思维：通过将问题转化为查找数列中是否存在某个数 A=B+CA = B + CA=B+C，我们避免了枚举所有数对的低效方法。这是典型的通过数学转化优化问题的思路。

时间与空间复杂度：学习如何平衡时间和空间复杂度。通过使用哈希表，虽然增加了额外的空间开销，但极大地提高了算法效率，适应了问题的大数据规模。

实际应用：哈希表和集合操作在实际开发中有着广泛应用，例如数据库的索引、缓存系统等，了解并掌握这些基本数据结构对解决实际问题至关重要。

三.分巧克力

1.对应思路

题目要求我们从 N 块巧克力中切出 K 块正方形巧克力，且每块正方形的边长尽可能大。我们需要通过切割巧克力的长方形，得到大小相同的正方形。

问题分析：

正方形的大小：
- 对于每一块巧克力 Hi×WiH_i \times W_iHi×Wi，我们能够从中切出多少个 S×SS \times SS×S 的正方形（其中 SSS 为正方形的边长）？
- 我们可以通过将 HiH_iHi 和 WiW_iWi 分别除以 SSS，计算每个长方形可以切出的正方形数量：个数=⌊HiS⌋×⌊WiS⌋\text{个数} = \left\lfloor \frac{H_i}{S} \right\rfloor \times \left\lfloor \frac{W_i}{S} \right\rfloor个数=⌊SHi⌋×⌊SWi⌋
- 我们需要找到一个 SSS，使得从所有 NNN 块巧克力中切出的正方形总数至少为 KKK。
二分查找：
- 由于我们希望切出的正方形边长尽可能大，最直观的办法是使用二分查找来确定边长 SSS 的最大值。范围从 1 到每块巧克力的最大边长（即 min⁡(Hi,Wi)\min(H_i, W_i)min(Hi,Wi)）。
检查条件：
- 对于每个 SSS，我们计算出所有巧克力切出的正方形数量，并判断是否能够满足至少有 KKK 块巧克力。如果能满足，说明 SSS 是一个可能的解，我们可以继续尝试更大的 SSS；否则，尝试更小的 SSS。

2.代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 判断给定边长 S 能否从所有巧克力中切出至少 K 块正方形
bool canCutSquares(const vector<pair<int, int>>& chocolates, int S, int K) {
    long long totalCount = 0;  // 记录切出的正方形总数
    for (const auto& chocolate : chocolates) {
        int H = chocolate.first;
        int W = chocolate.second;
        totalCount += (H / S) * (W / S);  // 计算该巧克力能切出多少个 S * S 的正方形
        if (totalCount >= K) return true;  // 如果已达到要求的数量，提前返回
    }
    return totalCount >= K;
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<pair<int, int>> chocolates(N);
    int maxSide = 0;


    for (int i = 0; i < N; ++i) {
        cin >> chocolates[i].first >> chocolates[i].second;
        maxSide = max(maxSide, min(chocolates[i].first, chocolates[i].second));
    }

    int low = 1, high = maxSide, bestSide = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (canCutSquares(chocolates, mid, K)) {
            bestSide = mid;  
            low = mid + 1;  
        } else {
            high = mid - 1;  
        }
    }

    cout << bestSide << endl; 
    return 0;
}

3.学习总结

二分查找的应用：通过二分查找可以高效地求解正方形的最大边长，尤其是在边长空间较大时，能够显著降低时间复杂度。

空间利用：通过使用哈希表和二分查找，我们在时间和空间上达到了较优的平衡，能够处理最大规模的数据。

问题的数学转化：通过将切割问题转化为数目判断问题，利用二分查找可以有效避免暴力破解的高时间复杂度。

四.卡牌

1.对应思路

减少重复计算：

在 canMakeKSets 函数中，我们每次都需要计算空白卡牌的数量。考虑到 a[i] 和 b[i] 对于每个卡牌是固定的，我们可以提前计算每种卡牌的补充量，然后直接通过前缀和计算每个 k 的所需补充卡牌数。

通过前缀和优化卡牌需求计算：

计算需要补充的空白卡牌数时，如果我们能提前计算出每种卡牌在每个 k 值下需要多少空白卡牌，可以加速查找。
我们可以使用 贪心策略 或者 扫描算法，避免每次都全量扫描 n 个卡牌。

2.代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5;
int n, m, a[N + 5], b[N + 5];

inline int read() {
    int x = 0;
    bool f = 1;
    char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) f ^= (ch == '-');
    for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return f ? x : -x;
}


bool check(int mid) {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        cnt += max(0LL, mid - a[i]);
    }
    return cnt <= m;  
}

void Kafka() {
    n = read();
    m = read();
    
    int L = 1, R = n * 2;
 
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }


    for (int i = 1; i <= n; ++i) {
        b[i] = read();
        R = min(a[i] + b[i], R);  
    }

    // 二分查找最大套牌数
    while (L < R) {
        int mid = (L + R + 1) >> 1;
        if (check(mid)) {
            L = mid;  
        } else {
            R = mid - 1; 
        }
    }

    cout << L << '\n';  
}

signed main() {
    Kafka();
    return 0;
}

3.学习总结

提前计算补充数量：通过一次遍历计算每个 k 需要的补充卡牌数量，可以减少时间复杂度，避免重复计算。

二分查找的技巧：通过二分查找可以有效缩小搜索范围，每次判断可以集中判断某个 k 是否可行。

空间优化：只使用简单的数组来存储卡牌数量和补充限制，空间复杂度为 O(n)，符合题目要求。

五.书的复制

1.对应思路

本题目要求将 m 本有顺序的书分给 k 个人复制，每个人抄写的书是连续的，并且需要尽可能最短的复制时间。复制时间指的是抄写页数最多的人所用的时间，目标是尽可能减少这个时间。

为了解决这个问题，采用了 二分查找 和 贪心算法 结合的策略：

二分查找：
- 对于复制时间的最大值 max_time（即抄写页数最多的人的时间），我们可以进行二分查找。
- 初始时，设置 L = 1（最小值）和 R = sum(a)（最大值，所有书页加起来）。
- 对于每个中间值 mid，我们要判断是否能在 mid 的最大时间限制下，合理分配书籍给 k 个人。
贪心算法：
- 每次尝试用当前的 mid 来分配书籍：从书籍列表中依次分配，如果当前人的已分配页数超过 mid，就开始分配给下一个人。
- 通过这种方式，我们可以确定在当前的 mid 时间下，能分配给 k 个人。
过程描述：
- 对于每次二分查找的 mid，我们从第 1 个人开始，贪心地分配书籍。如果当前书籍无法分配给当前人（超出了 mid 时间），就换给下一个人，直到所有书籍分配完。
- 如果我们能够在 k 个人内完成分配，那么说明当前的 mid 值是可行的，我们尝试缩小 mid；否则，增大 mid。
结果输出：
- 二分查找结束后，最终的最优时间就是 L，然后根据该时间输出每个人抄写的书籍区间。

2.代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int K=500;
int m,k,a[K+5];
int st[K+5],ed[K+5];
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
bool check(int mid)
{
    int cnt=1,now=mid;
    for(int i=1;i<=m&&cnt<=k;++i) 
    {
        if(a[i]>now) ++cnt,--i,now=mid;
        else now-=a[i];
    }
    return cnt<=k;
}
void Kafka()
{
    m=read(),k=read();
    int L=1,R=0;
    for(int i=1;i<=m;++i) a[i]=read(),R+=a[i];
    for(int mid=L+R>>1;L<R;check(mid)?R=mid:L=mid+1)mid=L+R>>1;
    ed[k]=m,st[1]=1;
    for(int i=k,j=m,now=L;i;--i)
    {
        for(;now>=a[j]&&j;--j) now-=a[j];
        st[i]=j+1,ed[i-1]=j,now=L;
    }
    
    for(int i=1;i<=k;++i) cout<<st[i]<<' '<<ed[i]<<'\n';
}
signed main()
{
    Kafka();
    return 0;
}

3.学习总结

本题考察了 二分查找 和 贪心算法 的结合使用。通过二分查找高效地探索最优解空间，再结合贪心算法快速判断是否能在指定时间内完成分配，使得问题得以高效解决。这种类型的问题不仅能够加深对算法思维的理解，还能帮助解决实际中遇到的类似最优化问题。

六.青蛙过河

1.对应思路

题目要求小青蛙在河对岸和学校之间来回跳跃，以最小化跳跃的能力（即最小的跳跃距离）。每次小青蛙必须从一块石头起跳，并且跳跃的距离不能超过某个值。为了确保小青蛙能够完成指定的跳跃次数（2x次），我们需要找到一个合适的跳跃距离，使得它能够在有限的跳跃次数内成功完成任务。

首先我们需要确定最小跳跃能力的范围。最小值为 1，最大值为 n-1（即河宽度），即从河的起点到终点的最大跳跃距离。
我们可以使用二分查找来缩小跳跃能力的范围。通过不断尝试不同的跳跃能力 mid，并判断是否能够完成 2x 次跳跃。
为了判断某个跳跃能力是否合适，模拟小青蛙的跳跃过程：从起点开始，每次尝试跳跃尽可能远的石头（跳跃的距离不超过当前的 mid），并尽量减少跳跃的次数。
如果跳跃次数小于或等于 2x，则当前跳跃能力 mid 是可行的。
否则，当前跳跃能力 mid 太小，不能完成任务。
通过二分查找不断调整跳跃能力的范围，直到找到最小的可行跳跃能力。

2.代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5;
int n, x, H[N + 5], sum[N + 5];

inline int read() {
    int x = 0; bool f = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) f ^= (ch == '-');
    for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return f ? x : -x;
}

bool check(int mid) {
    int cnt = 0, last = 0;
    for (int i = 1; i < n; i++) {
        if (i - last > mid) {
            cnt++;
            last = i - 1;
        }
    }
    if (n - last > mid) cnt++;
    return cnt <= 2 * x;
}

void Kafka() {
    n = read(), x = read();
    
    for (int i = 1; i < n; i++) {
        H[i] = read();
    }

    int L = 1, R = n, ans = n;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (check(mid)) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }

    cout << ans << '\n';
}

signed main() {
    Kafka();
    return 0;
}

3.学习总结

二分查找的应用
二分查找通常用来在有序区间中查找某个满足条件的值。在本题中，我们通过二分查找来找到最小的跳跃能力，这种问题通常被称为“最小最大化问题”。

模拟问题的实现
本题中模拟了小青蛙的跳跃过程，模拟的关键是如何判断是否能在有限的跳跃次数内完成任务。通过检查每个 mid 跳跃能力是否能够完成 2x 次跳跃，判断当前跳跃能力的可行性。

问题求解中的二分查找优化
由于本题的跳跃能力是一个整数范围，且通过验证跳跃能力的可行性可以在常数时间内完成，所以二分查找在这个问题中是一种高效的求解方法。

复杂度分析

二分查找的时间复杂度是 O(log n)。
对每个 mid 值，我们需要遍历石头进行一次跳跃模拟，最坏情况下是 O(n)。
因此，总的时间复杂度是 O(n log n)，对于 n 最大为 10^5 的数据，能够有效地在时间限制内完成计算。