01/10/2018, 09:13

Giúp đỡ bài tập giải thuật tìm kiếm và sắp xếp

spoj.com

SPOJ.com - Problem P155SUMD

...


P155SUMD - ROUND 5D - Chỉ là sắp xếp
Cho 2 dãy số, dãy a[] có n phần tử, dãy b[] có m phần tử.

Yêu cầu : In ra m dòng, dòng thứ i là số lượng số trong dãy a nhỏ hơn hoặc bằng b[i].

Input
Dòng đầu tiên chứa 2 số n, m lần lượt là số lượng phần tử của 2 dãy a[], b[].

Dòng thứ 2 chứa n số nguyên a[1], a[2], … a[n].

M dòng tiếp theo mỗi dòng chứa 1 số nguyên b[1], b[2], … b[m]

(1 <= n, m, a[i], b[i] <= 10^6)

Output
In ra kết quả bài toán.

Example
Input:
5 3

1 2 3 4 5

2

3

4

Output:
2

3

4

Đây là đoạn mã của mình , mình đã thử với một số trường hợp kết quả đưa ra đúng mà khi submit lại WRONG ANSWER

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#define nmax 1000000
int a[nmax],b[nmax];
int n,m;
using namespace std;
int compare( const void * a , const void * b ) {
    return ( * (int * ) a - * (int * ) b );
}
void xuli() {
    cin>>n>>m;
    for(int i = 0 ; i < n ;i++) {
        cin>>a[i];
    }
    for ( int i = 0 ; i < m ; i++) {
        cin>>b[i];
    }
    // sort array
    qsort(a,n,sizeof(int),compare);
    qsort(b,m,sizeof(int),compare);
 }
void process(int z , int x) {
    int s=0;
    for ( int i =0 ; i <= x ; i++ ){
        if ( z >= a[i] ) s++;
    }
    cout << s;
}
int binarysearch(int a[] , int first , int last , int x) {
    int mid = (first+last)/2;
    if ( x <= a[mid] ) {
        process(x,mid);
    }
    if ( x > a[mid]) {
        if (mid >= last) {
            cout << n;
        }
        else {
        return(binarysearch(a, mid+1, last, x));
        }
    }
    return 0;
}
int main(){
    xuli();
    for ( int i=0 ; i< m ; i++ ) {
        binarysearch(a,0,n-1,b[i]);
    }
    return 0;
}
Dat Thanh Vu viết 11:20 ngày 01/10/2018

Thuat toan cua ban chay qua thoi gian roi . Neu lam nhu ban minh hoi lam gi nua ban

Nguyen Gia Huy viết 11:21 ngày 01/10/2018

à để mình xem lại mình PTIT HCM sao không biết cái này ta

*grab popcorn* viết 11:23 ngày 01/10/2018

Có thể bạn in chưa đúng format đề yêu cầu. (Test thì thấy in kq liền nhau)

Góp vui giải thuật của mình
http://ideone.com/WYhW0M

Dat Thanh Vu viết 11:26 ngày 01/10/2018

Uh mình cùng in kết quả mình nghĩ là đúng .

Dat Thanh Vu viết 11:15 ngày 01/10/2018

Bạn xem mình in sai ở đâu được không nhỉ

*grab popcorn* viết 11:15 ngày 01/10/2018

Test sai:

5 5
1 1 1 1 1
1 2 3 4 5
-> 3 5 5 5 5
Đoán ẩu là do bạn chặt nhị phân bị thiếu lúc x <= mid

Dat Thanh Vu viết 11:27 ngày 01/10/2018

Cảm ơn drgnz nhe , mình sẽ debug lại

Gió viết 11:29 ngày 01/10/2018

Bài này bạn nên để ý tới giới hạn dữ liệu:

  • có thể dùng 1 mảng cnt[x] để đếm số phần tử = x
  • cộng dồn từ trái qua sẽ được cnt[x] là số phần tử <=x

sau khi xử lý: với mỗi b[i] chỉ cần in kq cnt[b[i]]

Bài liên quan
0