Problem 10919 Prerequisities?，畢業

讀入此學生修課通過的課程編號，用陣列接收，並且排序，再讀入課程類別課程數量以及必須通過課程的數量，接著一筆一筆讀入此課程類別的所有課程編號，比對修課通過的課程編號，累計數量後，大於等於此課程類別就代表此課程類別通過。如此將所有課程類別判斷過一次，如果沒有不通過的，就代表他會畢業。

此處如果輸入數量多的話，可以利用輸入優化來讀入整數或小數，而大家可以參網友「藍丫」提供的輸入優化 這函式讀入整數，如果數量一大，幾乎可以縮短一半以上的時間。感謝網友提供的輸入優化函式。而此函式程式碼如下：

#define SIZE 101

int classID[SIZE];
int index, n, m, c, r;

int getInt()
{
    char ch;
    int n = 0;
    while( ch = getchar())
        if(ch != ' ' && ch != '\n') break;
    n = ch - 48;
    while( ch = getchar())
    {
        if(ch == ' ' || ch == '\n') break;
        n = n * 10 + ch - 48;
    }
    return n;
}

所以可利用函式讀取修課通過的數量，排序好後，課程可用二分搜尋法來找尋是否有此課程。最後判斷他是否會畢業。

int isFind(int low, int high, int n)
{
    int mid;
    if (low > high) return -1;
    else
    {
        mid = (low + high) / 2;
        if (n == classID[mid])
            return mid;
        else if (n < classID[mid])
            return isFind(low, mid - 1, n);
        else 
            return isFind(mid + 1, high, n);
    }
}

主程式內 ....
while ((n = getInt()))
{
    index = 0;
    m = getInt();
    while (n --)
    {
        id = getInt();
        classID[index] = id;
        for (i = index; i >= 1; i --)
            if (classID[i] < classID[i - 1])
                tmp = classID[i], classID[i] = classID[i - 1], classID[i - 1] = tmp;
            else break;
        index ++;    
    }
    int error = 0, f;
    while (m --)
    {
        c = getInt(), r = getInt();
        int count = 0, find;
        while (c --)
        {
            f = getInt();
            find = isFind(0, index, f);
            if (find != -1) count ++;
        }
        if (count < r) error = 1; 
    }
    if (error) puts("no");
    else puts("yes");
}

By David.K

p10919題目連結
回ACM題庫目錄
回首頁