我|看看|不不|懂懂|别|人|写|的|代|码|，|有|没|有|人|讲|一|下

Question

我看不懂别人写的代码，有没有人讲一下
c++
题目
有 n
个线性序列，第 i
个序 列可以表示成 ki×x+bi
的形式（x=0,1,2,…）。
请问将这些序列的数合并起来后，第 m
小的数是多少（重复出现的数合并后也会多次出现）。
输入格式
输入第一行一个数 n
接下来 n
行每行两个数表示 ki,bi
最后一行一个数 m
输出格式
输出一个数表示答案。

样例输入
2
1 2
5 2
8
样例输出
7

数据规模
对于 100%的数据，保证 1≤n≤100000,1≤m≤100000,1≤ki,bi≤1000

这下面的是代码，但是我没没有看懂，有没有人再帮我详细的讲一下，谢谢！

#include<bits/stdc++.h>
using namespace std;
int n,m,k[100001],b[100001];
long long calc(int x){
    long long y=0;
    for(int i=1;i<=n;i++){
        if(b[i]<=x)
        y+=(x-b[i])/k[i]+1;
    }
    return y;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&k[i],&b[i]);
    }
    scanf("%d",&m);
    int L=0,R=1<<30;
    while(L+1<R){
        int w=(L+R)/2;
        if(calc(w)<m){
            L=w;
        }
        else{
            R=w;
        }
    }
    printf("%d\n",R);
    return 0;
}

Answer 1

这段代码是用来解决一个特定的问题的：给定多个线性序列，每个序列可以表示为 ( k_i \times x + b_i ) 的形式，其中 ( x ) 是一个非负整数（0, 1, 2, ...），( k_i ) 和 ( b_i ) 是序列的特定系数。问题要求找到合并这些序列后第 ( m ) 小的数。

下面是代码的详细解释：

头文件和命名空间

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

• #include<bits/stdc++.h>：这是一个包含了几乎所有标准库的头文件，常用于竞赛编程。
• using namespace std;：这允许你直接使用标准库中的名称，而不需要前缀 std::。

全局变量

int n, m, k[100001], b[100001];

• n：序列的数量。
• m：需要找到的第 ( m ) 小的数。
• k[100001]：存储每个序列的 ( k_i ) 值。
• b[100001]：存储每个序列的 ( b_i ) 值。

函数 calc

long long calc(int x){
    long long y = 0;
    for(int i = 1; i <= n; i++){
        if(b[i] <= x)
            y += (x - b[i]) / k[i] + 1;
    }
    return y;
}

• 这个函数计算当 ( x ) 等于某个特定值时，所有序列合并后小于等于 ( k_i \times x + b_i ) 的数的数量。
• if (b[i] <= x)：检查对于特定的 ( x )，序列 ( k_i \times x + b_i ) 是否有效（即 ( b_i \leq x )）。
• y += (x - b[i]) / k[i] + 1;：对于每个有效的序列，计算小于等于 ( x ) 的最大整数 ( x ) 的数量。这里 ( (x - b[i]) / k[i] ) 计算在当前 ( x ) 值下，序列 ( k_i \times x + b_i ) 能取到的最大整数 ( x ) 的数量。

主函数 main

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &k[i], &b[i]);
    }
    scanf("%d", &m);
    int L = 0, R = 1<<30;
    while(L + 1 < R){
        int w = (L + R) / 2;
        if(calc(w) < m){
            L = w;
        }
        else{
            R = w;
        }
    }
    printf("%d\n", R);
    return 0;
}

• 首先，读取序列的数量 n 和每个序列的 ( k_i ) 和 ( b_i )。
• 然后，读取 ( m )，即需要找到的第 ( m ) 小的数。
• 使用二分搜索来找到第 ( m ) 小的数。初始化搜索范围 L 和 R。
• 在每次迭代中，计算中间值 w 并使用 calc 函数检查小于等于 w 的数的数量。
• 如果 calc(w) < m，则说明 w 太小，需要增加，因此将 L 设置为 w。
• 否则，w 可能太大或合适，将 R 设置为 w。
• 当 L 和 R 收敛到一个值时，输出 R 作为答案。

这段代码通过二分搜索有效地找到了第 ( m ) 小的数，避免了暴力搜索的高时间复杂度。