NENUACM 二分习题课

NENUACM培训二分专题 – Virtual Judge

A – 查找

Description

输入 nn 个不超过 109109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,ana1,a2,…,a**n，然后进行 mm 次询问。对于每次询问，给出一个整数 qq，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1−1 。

Input

第一行 22 个整数 nn 和 mm，表示数字个数和询问次数。

第二行 nn 个整数，表示这些待查询的数字。

第三行 mm 个整数，表示询问这些数字的编号，从 11 开始编号。

Output

输出一行，mm 个整数，以空格隔开，表示答案。

Sample 1

Inputcopy Outputcopy
11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6 1 2 -1

Hint

数据保证，1≤n≤1061≤n≤106，0≤ai,q≤1090≤a**i,q≤109，1≤m≤1051≤m≤105

本题输入输出量较大，请使用较快的 IO 方式。

Inputcopy	Outputcopy
`11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6`	`1 2 -1`

代码二分STL：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int a[MAXN];
int main(){
    int n,m;
    cin >> n >> m;
    // 已经保证了单调不减
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    while(m--){
        int q;
        cin >> q;
        int res = lower_bound(a + 1,a + n + 1,q) - a;
        if(a[res] == q){
            cout << res << " ";
        }else{
            cout << -1 << " ";
        }
    }
}

代码手写二分：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int a[MAXN];
int main(){
    int n,m;
    cin >> n >> m;
    // 已经保证了单调不减
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    while(m--){
        int q;
        cin >> q;
        int l = 1,r = n;
        while(l < r){
            int mid = (l + r) >> 1;
            if(a[mid] >= q) r = mid;
            else l = mid + 1;
        }
        if(a[l] == q){
            cout << l << " ";
        }else{
            cout << -1 << " ";
        }
    }
}

B – 切绳子

Description

有 NN 条绳子，它们的长度分别为 LiL**i。如果从它们中切割出 KK 条长度相同的绳子，这 KK 条绳子每条最长能有多长？答案保留到小数点后 22 位(直接舍掉 22 位后的小数)。

Input

第一行两个整数 NN 和 KK，接下来 NN 行，描述了每条绳子的长度 LiL**i 。

Output

切割后每条绳子的最大长度。答案与标准答案误差不超过 0.010.01 或者相对误差不超过 1%1% 即可通过。

Sample 1

Inputcopy Outputcopy
4 11 8.02 7.43 4.57 5.39 2.00

Hint

对于 100%100% 的数据 0<Li≤100000.00,0<n≤10000,0<k≤100000<L**i≤100000.00,0<n≤10000,0<k≤10000

Inputcopy	Outputcopy
`4 11 8.02 7.43 4.57 5.39`	`2.00`

代码整数二分：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int a[MAXN];
int n,k;
int cal(int mid){
    int ans = 0;
    for(int i = 1;i <= n;i++){
        ans += a[i] / mid;
    }
    return ans;
}

int main(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        double temp;
        cin >> temp;
        a[i] = temp * 100;
    }

    int l = 0,r = 100000000;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(cal(mid) >= k){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    double ans = l / 100.0;
    cout << fixed << setprecision(2) << ans << "\n";
}

代码浮点二分【精度问题】：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
double a[MAXN];
int n,k;
int cal(double mid){
    int ans = 0;
    for(int i = 1;i <= n;i++){
        ans += (int)(a[i] / mid);
    }
    return ans;
}

int main(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }

    double l = 0.0,r = 100000.0;
    int cnt = 1;
    while(cnt <= 100){
        cnt++; // 这里我们使用次数来决定精度，否则不好处理
        double mid = (l + r) / 2.0;
        // 我们要找到最后一个大于等于的 尽可能往右边找（因为合法答案可能是个范围）
        if(cal(mid) >= k){
            l = mid; // 此时算多了，说明mid小了，要往右边找
        }else{
            r = mid;
        }
    }
    // 这里注意qwq 不要这么写 因为四舍五入
    // cout << fixed << setprecision(2) << l << "\n";
    int ans = l * 100;
    cout << fixed << setprecision(2) << ans / 100.0 << "\n";
}

C – A-B 数对

Background

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

Description

给出一串正整数数列以及一个正整数 CC，要求计算出所有满足 A−B=CA−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

Input

输入共两行。

第一行，两个正整数 N,CN,C。

第二行，NN 个正整数，作为要求处理的那串数。

Output

一行，表示该串正整数中包含的满足 A−B=CA−B=C 的数对的个数。

Sample 1

Inputcopy Outputcopy
4 1 1 1 2 3 3

Hint

对于 75%75% 的数据，1≤N≤20001≤N≤2000。

对于 100%100% 的数据，1≤N≤2×1051≤N≤2×105，0≤ai<2300≤a**i<230，1≤C<2301≤C<230。

2017/4/29 新添数据两组

Inputcopy	Outputcopy
`4 1 1 1 2 3`	`3`

代码二分：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int a[MAXN];
int main(){
    int n,c;
    cin >> n >> c;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    sort(a + 1,a + n + 1);
    long long ans = 0;
    for(int i = 1;i <= n;i++){
        // 假设每个数字都是数字b
        // 找a数字是否存在
        // 符合的a的数量是 == a 的那几个，可以用下面这种写法处理
        ans += (upper_bound(a + 1,a + n + 1,a[i] + c) - a) - (lower_bound(a + 1,a + n + 1,a[i] + c) - a);
    }
    cout << ans << "\n";
}

代码 map：

#include<bits/stdc++.h>
using namespace std;
map<int, int> freq;
int arr[200005];
int main() {
    int n, c;
    cin >> n >> c;

    // 读取数组并更新哈希表
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        freq[arr[i]]++;  // 当前数的个数++
    }

    long long ans = 0;

    // 计算符合条件的数对个数
    for (int i = 1; i <= n; i++) {
        ans += freq[arr[i] + c];  // 相差为c的数的个数
    }

    cout << ans << "\n";
}

D – 烦恼的高考志愿

Background

计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

Description

现有 mm 所学校，每所学校预计分数线是 aia**i。有 nn 位学生，估分分别为 bib**i。

根据 nn 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

Input

第一行读入两个整数 m,nm,n。mm 表示学校数，nn 表示学生数。

第二行共有 mm 个数，表示 mm 个学校的预计录取分数。第三行有 nn 个数，表示 nn 个学生的估分成绩。

Output

输出一行，为最小的不满度之和。

Sample 1

Inputcopy Outputcopy
4 3 513 598 567 689 500 600 550 32

Hint

数据范围：

对于 30%30% 的数据，1≤n,m≤10001≤n,m≤1000，估分和录取线 ≤10000≤10000；

对于 100%100% 的数据，1≤n,m≤1000001≤n,m≤100000，估分和录取线 ≤1000000≤1000000 且均为非负整数。

Inputcopy	Outputcopy
`4 3 513 598 567 689 500 600 550`	`32`

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int a[MAXN];

int main() {
    int m,n;
    cin >> m >> n;
    for(int i = 1;i <= m;i++){
        cin >> a[i];
    }
    sort(a + 1,a + m + 1);
    long long ans = 0;
    for(int i = 1;i <= n;i++){
        int q;
        cin >> q; // 学生分数
        int index = lower_bound(a + 1,a + m + 1,q) - a; // 找一下大于等于q的位置
        if(index == m + 1){ // 分数比学校还大
            ans += q - a[index - 1];
        }else if(index == 1){ // 分数小于等于最小的学校
            ans += a[1] - q;
        }else{
            ans += min(abs(a[index] - q),abs(q - a[index - 1])); // 前面一所和后面一所中选择一个
        }
    }
    cout << ans << "\n";
}

E – 解方程

对于方程 2018 * x ^ 4 + 21 * x + 5 * x ^ 3 + 5 * x ^ 2 + 14 = Y，告诉你Y的值，你能找出方程在0~100之间的解吗？

Input
第一行输入一个正整数T（表示样例个数）
接下来T组样例
每组样例一行，输入一个实数Y
Output
一行输出一个样例对应的结果，
输出方程在0~100之间的解，保留小数点后4位小数；如果不存在，输出 -1
Sample 1

Inputcopy Outputcopy
2 1 20180421 -1 9.9993

Inputcopy	Outputcopy
`2 1 20180421`	`-1 9.9993`

代码：

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

int main() {
    int n;
    cin >> n;
    while (n--) {
        double r = 100, l = 0, m, y;
        cin >> y;
        int cnt = 0;
        while(cnt < 1000) {
            cnt++;
            m = (r + l) / 2;
            if (2018 * m * m * m * m + 21 * m + 5 * m * m * m + 5 * m * m + 14 < y)
                l = m;
            else
                r = m;
        }
        if (l == 0 || r == 100)
            cout << "-1\n";
        else
            cout << fixed << setprecision(4) << m << "\n";
    }
}

F – 跳石头

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

Input
输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N 行，每行一个整数，第 i 行的整数 Di（0 < Di < L）表示第 i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
Output
输出文件只包含一个整数，即最短跳跃距离的最大值。
Sample 1

Inputcopy Outputcopy
25 5 2 2 11 14 17 21 4
将与起点距离为 2 和14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离17的岩石跳到距离 21的岩石，或者从距离 21 的岩石跳到终点）。
Note
对于20%的数据，0 ≤ M ≤ N ≤ 10。
对于50%的数据，0 ≤  M ≤ N ≤ 100。
对于100%的数据，0 ≤ M ≤ N ≤ 50,000，1 ≤ L ≤ 1,000,000,000。

Inputcopy	Outputcopy
`25 5 2 2 11 14 17 21`	`4`

单调性分析：

对于任何给定的最小跳跃距离 x，如果我们可以通过移除 M 块岩石来使得最短跳跃距离至少为 x，那么对于任何更小的跳跃距离 x' < x，我们也肯定可以通过移除不超过 M 块岩石使得最短跳跃距离至少为 x'。也就是说，如果我们能够实现某个跳跃距离 x，则所有小于 x 的跳跃距离也是可行的。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
int  l,n,m;
int d[MAXN];
int check(int x){
    int ans = 0;
    int last = 0;
    for(int i = 1;i <= n;i++){
        // 如果当前岩石与上一个岩石的距离小于 x，我们就需要移除这个岩石
        if(d[i] - last < x) ans++;
            else last = d[i];
    }
    // 如果移除的岩石数量超过 M，说明跳跃距离 x 不可能成立
    if(ans > m) return 0;
    else return 1;
    
}
int main(){
    
    //二分最短跳跃距离
    int left,right,mid;
    cin >> l >> n >> m;
    left = 1,right = l;
    for(int i = 1;i <= n;++i){
        cin >> d[i];
    }
    while(left < right){
        mid = (left + right + 1) / 2;
        if(check(mid)) left = mid;
        else right = mid - 1;
    }
    cout << left << "\n";
    return 0;
}

G – 银行贷款

Description

当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。

Input

三个用空格隔开的正整数。

第一个整数表示贷款的原值 w0w0，第二个整数表示每月支付的分期付款金额 ww，第三个整数表示分期付款还清贷款所需的总月数 mm。

Output

一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 0.1%0.1%。

数据保证答案不超过 300.0%300.0%。

Sample 1

Inputcopy Outputcopy
1000 100 12 2.9

Hint

数据保证，1≤w0,w≤231−11≤w0,w≤231−1，1≤m≤30001≤m≤3000。

Inputcopy	Outputcopy
`1000 100 12`	`2.9`

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    double w0,w,m;
    cin >> w0 >> w >> m;
    double l = 0.0,r = 100000.0;
    while(r - l > 1e-7){
       
        double mid = (r + l) / 2.0; // 此时假设利息是mid
        double temp = w0;
        // 模拟一下m个月份
        for(int i = 1;i <= m;i++){
            temp = temp - w + temp * (mid / 100);
        }
        if(temp > 1e-7){
            r = mid; // 没还完，利率偏大
        }else{
            l = mid; // 还完了，利率偏小
        }
    }
    cout << fixed << setprecision(1) << l << "\n";
}

Description

Input

Output

Sample 1

Hint

代码 二分STL：

代码 手写二分：

Description

Input

Output

Sample 1

Hint

代码 整数二分：

代码 浮点二分【精度问题】：

Background

Description

Input

Output

Sample 1

Hint

代码 二分：

代码 map：

Background

Description

Input

Output

Sample 1

Hint

代码：

Input

Output

Sample 1

代码：

Input

Output

Sample 1

Note

单调性分析：

代码：

Description

Input

Output

Sample 1

Hint

代码：

发送评论 编辑评论

代码二分STL：

代码手写二分：

代码整数二分：

代码浮点二分【精度问题】：

代码二分：

发送评论编辑评论