求助一道二分题
  • 板块学术版
  • 楼主liuzimingc
  • 当前回复28
  • 已保存回复28
  • 发布时间2021/8/5 11:25
  • 上次更新2023/11/4 11:57:05
查看原帖
求助一道二分题
421781
liuzimingc楼主2021/8/5 11:25

RT,题目:

C市有n名犯罪嫌疑人被叫到公安局问话,有m名目击证人描述了罪犯的身高,经公安局核实,目击证人提供的身高与罪犯实际身高略有误差(目击证人提供的身高是最接近实际身高,且实际身高≤目击者提供身高)。现公安局将所有n名犯罪嫌疑人按身高从低到高站成一排(n个人身高各不相同),并把目击者提供的m个身高都给你,请你快速帮公安局找到罪犯。

输入共m+2行 第1行:n,m(m<n≤100000) 第2行:n个嫌疑人的身高(小数点后两位),用空格隔开 后m行:每行1个数,代表目击者提供的1个身高(小数点后两位) 此题可输入1个参考身高输出1名罪犯信息

m行,每行两个数,真实罪犯的排序编号和他的身高(用空格隔开) 若提供的身高找不到罪犯,该行输出“NO”

我的代码(两个样例都过了,00 分):

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
#define LL long long

int n, m;
double t;
struct node {
    int id;
    LL w;
} a[MAXN];
bool cmp(node a, node b) {
    return a.w < b.w;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        a[i].w = t * 100, a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    while (m--) {
        cin >> t;
        LL num = t * 100;
        if (num < a[1].w) puts("NO");
        else {
            int l = 1, r = n + 1, mid, ans;
            while (l < r) {
                mid = (l + r) / 2;
                if (a[mid].w <= num) ans = mid, l = mid + 1;
                else r = mid;
            }
            double res = a[ans].w / 100.0;
            printf("%d %.2lf\n", a[ans].id, res);
        }
    }
	return 0;
}
2021/8/5 11:25
加载中...