# 11570: 【原1570】number100

### 题目描述

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

# Description

## Sample Input

5 3
1 3 5 7 9
3 4 9


## Sample Output

3
3
0


## Sample Input

5 2
1 3 5 7 9
0 10


## Sample Output

5
0


## Limits

• 对于$$30\%$$的数据，$$N,T\leq 1000$$
• 对于$$70\%$$的数据，$$N,T\leq 100000$$, $$X_i,Y_i \leq 100000$$
• 对于$$100\%$$的数据，$$N,T\leq 100000$$, $$X_i,Y_i \leq 2,000,000,000$$, 所有数字均为非负整数。

## ligongzzz's solution

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

int *findNum(int *data,int dataSize, int num) {
if (dataSize == 0) return data-1;
if (data[dataSize / 2] == num) return data + dataSize / 2;
else if (data[dataSize / 2] < num) return findNum(data + dataSize / 2 + 1, dataSize - dataSize / 2 - 1, num);
else return findNum(data, dataSize / 2, num);
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, T;
cin >> N >> T;
int *NList = new int[N];

//为了提高输入输出速度，全部改用scanf和printf。（只有这样才可以通过OJ）
for (int i = 0; i < N; i++) {
cin >> NList[i];
}

for (int i = 0; i < T; i++) {
int temp;
cin >> temp;
if (i != T - 1)
cout<<N - 1 - int(findNum(NList, N, temp) - NList)<<endl;
else
cout<<N - 1 - int(findNum(NList, N, temp) - NList);
}
return 0;
}


## Neight99's solution

#include <iostream>

using namespace std;

int found(int *, int, int, int);

int main() {
int n, t;
int *N, *T;

scanf("%d", &n);
scanf("%d", &t);
N = new int[n];
T = new int[t];

for (int i = 0; i < n; i++) {
cin >> N[i];
}
for (int i = 0; i < t; i++) {
cin >> T[i];
}

for (int i = 0; i < t; i++) {
int m = found(N, T[i], 0, n - 1);
printf("%d\n", n - 1 - m);
}
}

int found(int *N, int n, int x, int y) {
int Middle = (x + y) / 2;
if (x == y) {
if (N[x] <= n) {
return x;
} else {
return x - 1;
}
} else {
if (N[Middle] <= n) {
return found(N, n, Middle + 1, y);
} else {
return found(N, n, x, Middle);
}
}
}


## skyzh's solution

#include <cstdio>
#include <algorithm>
using namespace std;

int X[100000], Y[100000];
int main() {
int N, T;
scanf("%d%d", &N, &T);
for (int i = 0; i < N; i++) scanf("%d", &X[i]);
for (int i = 0; i < T; i++) scanf("%d", &Y[i]);
for (int i = 0; i < T; i++) {
int pos = upper_bound(X, X + N, Y[i]) - X;
while(X[pos] == Y[i] && pos < N) ++pos;
printf("%d\n", N - pos);
}
return 0;
}


## yyong119's solution

#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 100010;
int n, m, i;
int a[MAXN];

int main() {

scanf("%d%d", &n, &m);
for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
while (m--) {
int tmp, l = 1, r = n, mid;
scanf("%d", &tmp);
while (l < r) {
mid = (l + r) >> 1;
if (tmp < a[mid]) r = mid - 1;
else l = mid + 1;
}
for (i = mid - 2; i <= mid + 2; ++i)
if (tmp < a[i]) break;
if (n - i + 1 >= 0) printf("%d\n", n - i + 1);
else printf("%d\n", 0);
}
return 0;
}