Problem 10026 Shoemaker's Problem，工作排序

本來我打算放棄解這題，不過 google 了一下，發現只須要用到排序，就能解決這一題。

假設有兩個工作要比較，d1, m1 和 d2, m2 (d 為工作天，m 為延遲罰金)，要比較它們的大小就讓它們工作天以及延遲罰金互乘，再去比較大小，則可很輕易的就排序出結果，例如： 3個工作天，延遲罰金 5 以及 4 個工作天，延遲罰金 7，而 3 * 7 > 4 * 5，則後者排序在前，前者排序在後。

關鍵程式碼如下：

#define SIZE 1001
struct Job
{
    int num;
    int wDay;
    int dMoney;
};
struct Job job[SIZE], r;

主程式內 ...

scanf("%d", &m);
for (i = 0; i < m; i ++)
{
    scanf("%d %d", &day ,&money);
    job[i].wDay = day, job[i].dMoney = money;
    job[i].num = i + 1;
    for (j = i; j >= 1; j --)
    {
        if (job[j].wDay * job[j - 1].dMoney < 
            job[j - 1].wDay * job[j].dMoney)
        {
            r = job[j], job[j] = job[j - 1],
            job[j - 1] = r;
        }
        else break;
    }
}

最後只要逐個印出 job 陣列內的 num 值就好了。

By David.K

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

Problem 10048 Audiophobia，噪音恐懼症

此題與 Problem 534 Frogger 用的方法一模一樣，只是這題更簡單了，因為它不需要算點與點之間的距離，它直接給你某路口走到某路口所經過的街道，噪音有多少分貝。

因為這一題有些地方不能直達，所以值還會是 0，所以我初始化就全部給他定 1000，噪音到 1000 分貝，耳膜也破了吧。再接著用最小路徑演算法，答案就會呼之欲出了。

for (i = 1; i <= C; i ++)
    for (j = 1; j <= C; j ++)
        W[i][j] = 1000;

for (i = 0; i < S; i ++)
{
    int noise, p1, p2;
    scanf("%d %d %d", &p1, &p2, &noise);
    W[p1][p2] = W[p2][p1] = noise;
}
for (k = 1; k <= C; k ++)
    for (i = 1; i <= C; i ++)
        for (j = 1; j <= C; j ++)
            if (i != j)
                W[i][j] = min(W[i][j], max(W[i][k], W[k][j]));
if (caseNum != 1) printf("\n");
printf("Case #%d\n", caseNum ++);
for (i = 1; i <= Q; i ++)
{
    int p1, p2;
    scanf("%d %d", &p1, &p2);
    int minNoise = W[p1][p2];
    if (minNoise != 1000) printf("%d\n", W[p1][p2]);
    else printf("no path\n");
}

By David.K

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

Problem 10015 Joseph's Cousin，吃人遊戲

此題為紐西蘭停電的進階版，因為他不是從頭到尾數同一個數，而是要吃掉第 i 個人，就要數第 i 個質數，直到吃剩最後一個人才停，要輸出這最後一個人在什麼位置。

我用的方法很粗糙，暴力破解，所以執行時間有點長，不過還是過了。

首先建立質數表，數值到 33000，就能把前 3502 的質數找出來：

#define SIZE 33000
int prime[SIZE + 1];
int prime_table[SIZE], prime_table_len = 0;

void makeprime(){
    int i, j;
    prime_table[prime_table_len ++] = 2;
    for(i = 3; i < SIZE; i += 2)
        if(!prime[i]){
            for(j = i + i; j <= SIZE; j += i)
                prime[j] = 1;
            prime_table[prime_table_len ++] = i;
        }
}

再用暴力破解即可，C 語言程式碼如下：

int nextLife(int isLife[], int site, int n)
{
    while (!isLife[site])
    {
        site ++;  
        if (site >= n) site -= n;
    }
    return site;
}

int main()
{
    makeprime();
    int n, i, j, life;
    while (scanf("%d", &n) == 1 && n)
    {
        int isLife[n], nowSite = 0, count;
        for (i = 0; i < n; i ++) /* 初始化 */
            isLife[i] = 1;
        for (i = 0; i < n - 1; i ++)
        {
            count = prime_table[i] - 1;
            
            for (j = 0; j < count; j ++)
            {
                nowSite = nextLife(isLife, nowSite, n);
                nowSite ++;
                if (nowSite >= n) nowSite -= n;
            }
            nowSite = nextLife(isLife, nowSite, n);
            isLife[nowSite] = 0;
        }
        for (i = 0; i < n; i ++)
            if (isLife[i]) { printf("%d\n", i + 1); break; }
        
    }
    return 0;
}

By David.K

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