user2737948 - 11 months ago 58

C Question

I'm learning C and I'm solving this challenge, I'm not planning to submit it to the uva platform and the reason I'm coding this exercise is for leaning, maybe is not the best approach to the problem but I'm trying.

The input I print in my terminal is the following:

`4`

3

20 30 40 50 30 40

Res: 2

4

20 30 10 10 30 20 40 50

Res: 4

3

10 30 20 20 30 10

Res: 2

4

10 10 20 30 40 50 39 51

Res: 3

The answers from each input test are incorrect and I believe the reason is the qsort function. I'm confuse about how to use the qsort function using a structure, I'm calling my structure that is called array, followed by the size of my input, then using sizeof(int) but do I need to use int or sizeof my structure, lastly I'm calling my compare function. My code is:

`#include <stdio.h>`

#include <string.h>

struct Dolls{

int w;

int h;

}array[20005];

int cmp(struct Dolls a, struct Dolls b){

if(a.w==b.w){

return a.h < b.h;

}else{

return a.w > b.w;

}

}

int arr[20005];

int dp[20005];

int n;

int bSearch(int num, int k){

int low=1;

int high = k;

int mid;

while(low<= high){

mid = (low+high)/2;

if(num>=dp[mid]){

low=mid+1;

}else{

high=mid-1;

}

}

return low;

}

int res_dolls(){

int k=1;

int i,pos;

dp[i]=arr[1];

for(i=2;i<=n;i++){

if(arr[i]>=dp[k]){

dp[++k] = arr[i];

}else{

pos = bSearch(arr[i],k);

dp[pos] = arr[i];

}

}

return k;

}

int main(){

int t,j;

scanf("%d",&t);

while(t--){

memset(array,0,sizeof(array));

scanf("%d",&n);

for(j=1;j<=n;j++){

scanf("%d %d",&array[j].w, &array[j].h);

}

qsort(array,n,sizeof(int),cmp);

for(j=1;j<=n;j++){

arr[j] = array[j].h;

}

printf("%d\n",res_dolls());

}

return 0;

}

Answer Source

Your `cmp`

function needs to be defined as `int (*)(const void *, const void *)`

for it to work for `qsort`

:

```
int cmp(const void *va, const void *vb){
const struct Dolls *a = va;
const struct Dolls *b = vb;
if(a->w > b->w) {
return 1;
} else if(a->w < b->w){
return -1;
} else if(a->h > b->h) {
return 1;
} else if(a->h < b->h){
return -1;
} else {
return 0;
}
}
```

As for the call to `qsort`

, you need to give it the size of an array element:

```
qsort(array,n,sizeof(struct Dolls),cmp);
```

EDIT:

Fixed the error with the parameter names. Also changed how the sort is performed to conform to how the comparison function must behave.