二分查找

 

A. 查找

题目描述：

输入 n (n≤10^6) 个不超过 10^9的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1​,a2​,…,an​，然后进行 m(m≤10^5) 次询问。
对于每次询问，给出一个整数 q(q≤10^9)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。

 

Input：

第一行 2 个整数 n 和 m，表示数字个数和询问次数。

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

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

 

Output：

m 个整数表示答案。

 

示例：

输入：
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出：
1 -2 1

 

思路：

正常二分查找。

 

代码：

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

int cac(vector<int> number, int x) {
    int left = 0, right = number.size() - 1, res = -1;
    while(left <= right){
        int mid = (left + right) / 2;
        if(number[mid] == x) {
            res = mid + 1;
            break;
        }
        else if(number[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> number(n);
    vector<int> nums(m);
    for(int i = 0; i < n; i++)
        cin >> number[i];
    number.erase(unique(number.begin(), number.end()), number.end()); //unique函数将重复的元素移到容器末尾，配合erase函数删除则达到去重的功能
    for(int j = 0; j < m; j++){
        cin >> nums[j];
        cout << cac(number, nums[j]) << " ";
    }
    return 0;
}

 

B. 烦恼的高考志愿

题目描述：

现有 m (m≤100000) 所学校，每所学校预计分数线是ai​(ai​≤10^6)。有 n (n≤100000) 位学生，估分分别为 bi​ (bi​≤10^6)。

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

 

Input:

第一行读入两个整数m,n。m表示学校数，n表示学生数。第二行共有m个数，表示m个学校的预计录取分数。第三行有n个数，表示n个学生的估分成绩。

 

Output:

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

 

示例：

输入：
4 3
513 598 567 689
500 600 550

输出：
32

 

思路：

在二分查找时，每次选出最小的差值。

 

代码：

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

int cac(vector<int> school, int b) {
    int left = 0, right = school.size() - 1, res = INT_MAX;
    while(left <= right){
        int mid = (left + right) / 2;
        if(school[mid] == b) {
            res = 0;
            break;
        }
        else if(school[mid] > b) {
            right = mid - 1;
            res = min(res, abs(school[mid] - b));
        }
        else {
            left = mid + 1;
            res = min(res, abs(school[mid] - b));
        }    
    }
    return res;
}

int main() {
    int m, n, ans = 0;
    cin >> m >> n;
    vector<int> school(m);
    vector<int> student(n);
    for(int i = 0; i < m; i++)
        cin >> school[i];
    sort(school.begin(), school.end());
    for(int i = 0; i < n; i++) {
        cin >> student[i];
        ans += cac(school, student[i]);    
    }
    cout << ans;
    return 0;
}

 

C. 银行贷款

题目描述：

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

 

Input:

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

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

 

Output:

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

 

示例：

输入：
1000 100 12

输出：
2.9

 

思路：

本题相较前两题考虑更多。

每年钱应为num * (1 + x) - m; 即每年的利率后本金减去需缴付的月资金，若本金耗尽则可还清，反之不可。

上网查询，国家规定月利率不得大于2.5% 则从 0 - 500 开始查找符合题意的情况。

 

代码：

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

bool cac(double x, int n, int m, int d) {
    double num = n;
    for(int i = 0; i < d; i++){
        num += num * x;
        num -= m;
    }
    if(num <= 0) return true;
    else return false;
}

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    double left = 0, right = 500, mid;
    for(int i = 0; i < 100; i++){
        mid = (left + right) / 2;
        if(cac(mid / 100, n, m, d)) left = mid;
        else right = mid;
    }
    printf("%.1lf", left);
    return 0;
}