poj 2028 When Can We Meet?

Memory: 176K

Time: 16MS

解题思路

题意：

       ICPC委员会要安排一个会议，但是成员们都太忙了，所以很难安排，所以要我们编程找个最合适的日子让更多的人来参加这个会议。

       一共有N个人，至少要Q个人参加，第i个人有mi天是有空的，分别是date1， date2…..datem，表示明天开始的第datei天，比如date1为1表示明天有空，date2为2表示后天有空，……要输出最好的那天，要求是参加的人尽可能多，如果用相同人数的要尽量靠前。

思路：

       从第1到max开始枚举，看多少人在第i天有空，如果用>=q的人有空的话，把人数跟i记录下来，放在结构体数组里，最后按人数从大到小排序，如果最大的那个的人数的话输出0，否则就是最大的那个，还要日子靠前的那个。

    Max是这么多人的有空的日子里最晚的那天，

 

源程序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 55
#define M 105
typedef struct
{
    int index;
    int count;
}item;
item items[M];

int cmp(const void *p, const void *q)
{
    return (*(int *)p) - (*(int *)q);
}

int cmp2(const void *p, const void *q)
{
    item *a = (item *)p;
    item *b = (item *)q;
    if(a->count > b->count)
        return -1;
    else if(a->count < b->count)
        return 1;
    else
    {
        return a->index > b->index ? 1 : -1;
    }
}
int main()
{
    int i, j, k;
    int size, quorum, dateNum, result, count, max;
    int dates[N][M];
    int *find;
    while(scanf("%d%d", &size, &quorum) && size && quorum)
    {
        memset(dates, 0, sizeof(dates));
        memset(items, 0, sizeof(items));
        max = 0;
        for(i=0; i<size; i++)
        {
            scanf("%d", &dates[i][0]);
            for(j=1; j<=dates[i][0]; j++)
            {
                scanf("%d", &dates[i][j]);
                if(max < dates[i][j])
                    max = dates[i][j];
            }
        }

        for(i=1, k=0; i<=max; i++)
        {
            for(j=0, count=0; j<size; j++)
            {
                find = (int *)bsearch(&i, dates[j]+1, dates[j][0], sizeof(dates[j][1]), cmp);
                if(find != NULL)
                {
                    count++;
                }
            }
            if(count >= quorum)
            {
                items[k].count = count;
                items[k].index = i;
                k++;
            }
            if(count == size)
                break;
        }
        qsort(items, k, sizeof(items[0]), cmp2);
        
        if(items[0].count >= quorum)
            printf("%d\n", items[0].index);
        else printf("0\n");
    }
    return 0;
}