议事大厅-【赛码网】..

【今日头条】第四道，计算两个数组A、B里下标相同位置分别大于x,y的元素数目

发布于 2017-03-30 21:32 3296 次浏览 2 赞最后一次编辑是 2017-03-30 21:34 来自笔试面试

有人还记得x, 和y的范围限制吗？

coder_CJD9FT5S

这道题是不是二分，竟然所有测试用例都不通过。好气哦

2017-03-30 21:36

coder_KMPX6KBV

1~10^5吧，我也只通过了30%的case，感觉是超时了或者内存超了。

我的代码，大家可以参考一下，顺便帮我查查错，谢谢！

#include <iostream> 
#include <vector>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    int* A = new int[n];
    int* B = new int[n];
    vector<int> res(q, 0);
    
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

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

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        for (int j = 0; j < n; j++) {
            if (A[j] >= x && B[j] >= y) {
                res[i]++;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << endl;
    }

    return 0;
}

2017-03-30 21:39

coder_9R4PK2A8

/**
 *
 * 思路：
 * 1. 对A数组希尔排序，B数组位置也相应变化，时间复杂度是O（nlogn）
 * 2. 遍历一趟查询，二分查找x，然后判断y，找到y后位置，output。时间复杂度是O（qlogn）
 *
 */
import java.util.Scanner;
public class Main04 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            // 初始化
            int n = scanner.nextInt();
            int q = scanner.nextInt();
            int[] A = new int[n];
            int[] B = new int[n];
            for (int i = 0; i < n; i++) {
                A[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                B[i] = scanner.nextInt();
            }
            // 对A进行希尔排序，B数组位置相应变化
            shellSort(A, B, n);

            int x, y;
            int[] counts = new int[q];
            for (int i = 0; i < q; i++) {
                x = scanner.nextInt();
                y = scanner.nextInt();
                // 二分查找满足条件x的位置
                int start = binarySearch(A, n, x);
                // 返回-1则表示不满足条件，continue
                if (start == -1)    continue;
                // 遍历B中中start至n-1
                for (int j = start; j < n; j++) {
                    if (B[j] >= y)
                        counts[i]++;
                }
            }
            for (int i = 0; i < q; i++) {
                System.out.println(counts[i]);
            }
        }
    }

    static int binarySearch(int[] A, int n, int target) {
        int left = 0;
        int right = n -1;
        if (target <= A[left])
            return left;
        if (target > A[right])
            return -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == A[mid]) {
                return mid;
            } else if (target < A[mid]) {
                if (target > A[mid - 1]) {
                    return mid;
                }
                right = mid - 1;
            } else {
                if (target < A[mid + 1]) {
                    return mid + 1;
                }
                left = mid + 1;
            }
        }
        return -1;
    }

    // 希尔排序
    static void shellSort(int[] A, int[] B, int n) {
        int tmpA, tmpB, j;
        for (int r = n / 2; r >= 1; r /= 2) {
            for (int i = r; i < n; i++) {
                tmpA = A[i];
                tmpB = B[i];
                j = i - r;
                while (j >= 0 && tmpA < A[j]) {
                    A[j + r] = A[j];
                    B[j + r] = B[j];
                    j -= r;
                }
                A[j + r] = tmpA;
                B[j + r] = tmpB;
            }
        }
    }
}

2017-03-31 11:36

coder_WX3GPKEC

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn],c[maxn];
int x[maxn],y[maxn],z[maxn];
int ans[maxn],sum[maxn];

bool cmp1(int i,int j){
	if(a[i]==a[j])return b[i]>b[j];
	return a[i]>a[j];
}
bool cmp2(int i,int j){
	if(x[i]==x[j])return y[i]>y[j];
	return x[i]>x[j];
}

int lowbit(int x){return x&(-x);}

int add(int x){
	while(x<maxn){
        c[x]++;
        x+=lowbit(x);
    }
}

int Sum(int x){
    int ret=0;
    while(x>0){
        ret+=sum[x];
        x-=lowbit(x);
    }
    return ret;
}
int main(){
	//freopen("in.txt","r",stdin);
	for(int i=1;i<maxn;i++)c[i]=i,z[i]=i;
	int n,q;
	cin>>n>>q;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	sort(c,c+n,cmp1);
	
	//离线
	for(int i=0;i<q;i++)cin>>x[i]>>y[i];
	sort(z,z+q,cmp2);
	
	int top=0;
	
	for(int i=0;i<q;i++){
		while(top<n&&a[c[top]]>=x[z[i]])add(b[c[top++]]);
		ans[z[i]]=top-Sum(y[z[i]]-1);
	}
	
	for(int i=0;i<q;i++)
		cout<<ans[i]<<endl;
	
	return 0;
}

2017-03-31 11:46

陈dream

哪里可以看原题啊，想重做一遍

2017-04-01 12:32