Problem 10664 Luggage，行李

此題讀入各行李重量後，以大到小排序，最後再平均分配在兩台車子上，如兩台車同重量，輸出 "YES"，否則，輸出 "NO"。

此處我也用到了輸入優化的方式。
關鍵程式碼如下：

#define SIZE 21

int luggage[SIZE], changeLine, index;

int getInt()
{
    char ch;
    int n = 0;
    changeLine = 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;
    }
    if (ch == '\n') changeLine = 1;
    return n;
}

主程式內 ....
index = 0, changeLine = 0, a = 0, b = 0;
while (!changeLine)
{
    luggage[index] = getInt();
    for (i = index; i >= 1; i --)
        if (luggage[i] > luggage[i - 1])
            tmp = luggage[i], luggage[i] = luggage[i - 1], luggage[i - 1] = tmp;
        else break;
    index ++;
}

for (i = 0; i < index; i ++)
{
    if (a == b) a += luggage[i];
    else if (a > b) b += luggage[i];
    else a += luggage[i];  
}

if (a == b) puts("YES");
else puts("NO");

By David.K

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

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題庫目錄
回首頁

Problem 10903 Rock-Paper-Scissors，剪刀石頭布

讀入兩整數 n 和 k，說明有 n 的人進行 k * n * (n-1) / 2 場剪刀石頭布的遊戲，要你算出最後每個人的勝率，而勝率為 w / (l + w) (註：w 為勝場數，l 為敗場數)。

創建一個結構陣列，紀錄每個人勝敗場次數，如以下程式碼：

#define SIZE 101

struct player
{
    int win;
    int lose;
};
struct player p[SIZE];

其實只要比較每場勝敗為誰，再將這些結果累加到每個人的陣列索引，最後印出勝率。C 語言程式碼如下：

scanf("%d", &k);
for (i = 1; i <= n; i ++)
    p[i].win = 0, p[i].lose = 0;
game = k * n * (n - 1) / 2;
while (game --)
{
    scanf("%d %s %d %s", &p1, f1, &p2, f2);
    int kind1, kind2;
    if (f1[0] == 'r') kind1 = 1;
    else if (f1[0] == 'p') kind1 = 2;
    else kind1 = 3;
    if (f2[0] == 'r') kind2 = 1;
    else if (f2[0] == 'p') kind2 = 2;
    else kind2 = 3;
    if (kind1 > kind2) 
    { 
        j = kind1 - kind2;
        if (j == 1) p[p1].win ++, p[p2].lose ++;
        else p[p2].win ++, p[p1].lose ++;
    }
    else if (kind1 < kind2)
    {
        j = kind2 - kind1;
        if (j == 1) p[p2].win ++, p[p1].lose ++;
        else p[p1].win ++, p[p2].lose ++;
    }
}
int total, win;
for (i = 1; i <= n; i ++)
{
    win = p[i].win;
    total = win + p[i].lose;
    if (total == 0) printf("-\n");
    else printf("%.3f\n",(float)win / (float)total);
}

By David.K

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