Skip to content

12109: 【原2109】二次方程

题目

题目描述

author: tomtao26 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2109

Description

小C最近正在研究二次方程，遇到了一些问题，希望你能帮他解决。现在有\(N\)个数，小C想知道，这\(N\)个数中有多少数作为\(a\)，才能使给定\(b\),\(c\)，对于\(ax^2 + bx + c = 0\)有实数解。

Input Format

一个整数\(N\)，表示有\(N\)个数。

接下来\(N\)行是这\(N\)个数\(a_i\) (\( a_i > 0\))。

随后一个整数\(K\)，表示有\(K\)个询问问题的\((b,c)\)对。

接下来\(k\)行，表示一个询问，每行两个数，分别是\(b\)和\(c\)(\(b,c > 0\))。

Output Format

每一行对于每个给定的询问，给出一个答案\(k_i\)，表示有对于第\(i\)个询问的\((b,c)\)有\(k_i\)个数满足要求。

Sample Input

3
1
2
3
2
6 2
3 2

Sample Output

3
1

Specification

\( N \leq 100000\); \( K \leq 10000\); \( b, c \leq 10000\); \( a_i \leq 100000\);

为方便起见，这\(N\)个数是已经从小到大排好序的。

BugenZhao's solution 

//
// Created by BugenZhao on 2019/3/17.
//
// 线性探测

#include <iostream>

using namespace std;

static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

int main() {
    int N;
    cin >> N;
    auto a = new int[N];
    int tmp;
    for (int i = 0; i < N; ++i) {
        cin >> tmp;
        a[i] = (-4) * tmp;
    }
    int K;
    cin >> K;
    int b, c;
    for (int j = 0; j < K; ++j) {
        cin >> b >> c;
        int count = 0;
        int b2 = b * b;
        for (int i = 0; i < N; ++i) {
            if (b2 + a[i] * c >= 0) {
                ++count;
            } else {
                break;
            }
        }
        cout << count << endl;
    }
    delete[] a;
    return 0;
}

FineArtz's solution 

/* 二次方程 */
#include <iostream>
#include <cmath>
using namespace std;

int a[100005] = {0};

int search(int low, int high, double dt){
    int l = low, h = high, m = (l + h) / 2;
    while (h > l){
        m = (l + h) / 2;
        if (abs(a[m] - dt) < 10e-6) return m + 1;
        if (a[m] < dt)
            l = m + 1;
        else
            h = m - 1;
    }
    return l;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> k;
    for (int i = 1; i <= k; ++i){
        int b, c, cnt = 0;
        cin >> b >> c;
        if (c == 0) cnt = n;
        else{
            double dt = b * b * 1.0 / 4 / c;
            if (a[1] > dt) cnt = 0;
            else cnt = search(1, n, dt);
        }
        cout << cnt << endl;
    }
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cmath"
#include "cstdio"
using namespace std;

int ai[100009] = { 0 };

int mid_find(int left, int right, int val) {
    if (left == right) {
        if (ai[left] <= val)
            return left;
        else return left - 1;
    }
    int mid = (left + right) >> 1;
    if (ai[mid] == val)
        return mid;
    else if (ai[mid] < val) {
        return mid_find(mid + 1, right, val);
    }
    else {
        return mid_find(left, mid - 1, val);
    }
}

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", &ai[i]);

    int K;
    scanf("%d", &K);
    for (int i = 0; i < K; ++i) {
        int b, c;
        scanf("%d %d", &b, &c);

        printf("%d\n", mid_find(0, N - 1, b * b / (4 * c)) + 1);
    }

    return 0;
}

LuminousXLB's solution 

// 2109. 二次方程
// #423574 正确 / 分数：100 / 时间：1123ms / 内存：11372kb
#include <cstdio>

bool delta(int a, int b2, int c) {
    int delta = b2 - 4 * a * c;

    return delta >= 0;
}


int main(int argc, char const *argv[]) {
    int N;

    scanf("%d", &N);
    int *num = new int[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", num + i);
    }

    int K, b, c;
    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
        scanf("%d %d", &b, &c);
        b = b * b;
        for (int j = 0; j < N; j++) {
            if (!delta(num[j], b, c)) {
                printf("%d\n", j);
                break;
            } else if (j == N - 1) {
                printf("%d\n", N);
            }
        }
    }

    delete[] num;
    return 0;
}

q4x3's solution 

/**
 * 二分
 * 找到不大于tmp的最大a，a[lo - 1] (a[lo]为比tmp大的最小a)
 * 故lo个a可以
 **/
#include <iostream>

using namespace std;

int N, K, lo, hi, mi;
double a[100233];

int main() {
    cin >> N;
    for(int i = 0;i < N;++ i) {
        scanf("%lf", &a[i]);
    }
    cin >> K;
    for(int i = 0;i < K;++ i) {
        double b, c;
        scanf("%lf%lf", &b, &c);
        double tmp = b * b / (4 * c);
        lo = 0; hi = N;
        while(lo < hi) {
            mi = (lo + hi) >> 1;
            if (tmp < a[mi]) {
                hi = mi;
            } else {
                lo = mi + 1;
            }
        }
        printf("%d\n", lo);
    }
    return 0;
}

skyzh's solution

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

double D[100000];

int main() {
    int N, K;
    double b, c;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%lf", &D[i]);
    }
    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
        scanf("%lf%lf", &b, &c);
        double _s = b * b / 4.0 / c;
        int pos = upper_bound(D, D + N, _s) - D;
        printf("%d\n", pos);
    }
    return 0;
}

victrid's solution 

#include <iostream>
#include <stdio.h>

using namespace std;

int bp(int N, int* spis, int poisk) {
    int min = 0, max = N - 1, mid;
    if (poisk >= spis[max])
        return N;
    if (poisk < spis[min])
        return 0;
    while (min <= max) {
        mid = (min + max) / 2;
        if (poisk == spis[mid])
            return mid + 1;
        else if (poisk < spis[mid])
            max = mid - 1;
        else
            min = mid + 1;
    }
    return 0;
}
int main() {
    //* scanf and printf to reduce time
    int N, k, b, c;
    cin >> N;
    int* spis = new int[N];
    for (int i = 0; i < N; i++)
        scanf("%d", spis + i);
    scanf("%d", &k);
    int* otv = new int[k];
    for (int i = 0; i < k; i++) {
        scanf("%d %d", &b, &c);
        otv[i] = bp(N, spis, (b * b / c / 4));
    }
    for (int i = 0; i < k; i++) {
        if (i)
            printf("\n");
        printf("%d", otv[i]);
    }
    return 0;
}