11570: 【原1570】number100

题目

题目描述

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

Description

二哥手上有N个数字，这些数字已经被二哥排好顺序了，二哥知道这里面有自己喜欢的T个数字。

现在他想知道对于自己喜欢的每一个数字，这n个数字中比它大的有多少个。N,T<=100,000

Input Format

第一行有两个整数N,T

接下来一行 N 个数代表二哥手上的数字{X_1,X_2,…,X_N}。

接下来一行 T 个数代表二哥喜欢的数字{Y_1,Y_2,…,Y_N}。

Output Format

每行输出一个数字，表示二哥手上的数字比这个喜欢的数字{Y_i}大的个数。

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