# 12109: 【原2109】二次方程

### 题目描述

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

## 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$$;

## 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;
}