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;
}
Thuat toan cua ban chay qua thoi gian roi . Neu lam nhu ban minh hoi lam gi nua ban
à để mình xem lại mình PTIT HCM sao không biết cái này ta
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
Uh mình cùng in kết quả mình nghĩ là đúng .
Bạn xem mình in sai ở đâu được không nhỉ
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
Cảm ơn drgnz nhe , mình sẽ debug lại
Bài này bạn nên để ý tới giới hạn dữ liệu:
cnt[x]
để đếm số phần tử = xcnt[x]
là số phần tử<=x
sau khi xử lý: với mỗi
b[i]
chỉ cần in kqcnt[b[i]]