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;
}
. Neu lam nhu ban minh hoi lam gi nua ban
mình PTIT HCM sao không biết cái này ta
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?