Week 08 - 作業講解

Neoj #991 - Sprouty Mart

Benson Chiu @ Sprout 2022

---

解題思路

• 對於每一個便利商店，我們尋找一個使 利潤最大 且 大於等於 0 的物流中心
• 因為商品價格皆相同，利潤取決於距離
• 如何決定送貨量？
  • 題目沒有特別指出物流中心的限制，故送貨量即為需求量
• 用兩個變數分別統計目前累積的銷貨毛利與未被滿足的需求

---

運用 Struct 進行適當的模組化

struct Rt
{
    int x;
    int y;
    int dmd;
};
struct Lg
{
    int u;
    int v;
};

---

距離也可以用函數包起來

int distMht(int x, int y, int u, int v)
{
    return abs(x - u) + abs(y - v);
}

---

輸入資料：以便利商店為例

Rt rtArr[1000];
for(int i = 0; i < m; i++)
{
    int x, y;
    cin >> x >> y;
    rtArr[i].x = x;
    rtArr[i].y = y;
    cin >> rtArr[i].dmd;
}

---

對於每一個零售店選擇一個獲利最大的物流中心

for(int i = 0; i < m; i++) //rt -> lg
{        
    int maxProfit = 0; //該零售店可獲得的最高利潤
    bool flag = false; //true:可以獲利 / false:所有物流中心
    for(int j = 0; j < n; j++)
    {
        int profit =  (p - c*distMht(rtArr[i].x,rtArr[i].y,lgArr[j].u,lgArr[j].v))*rtArr[i].dmd;
        if(profit >= maxProfit)
        {
            flag = true;
            maxProfit = profit;
        }
    }
    if(flag)
        sumProfit += maxProfit; //sumProfit -> 存取總銷貨毛利
    else
        remains += rtArr[i].dmd; //remains -> 存取未被滿足的需求

}

---

輸出結果

cout << sumProfit << "," << remains << endl;

---

完整程式碼

#include<iostream>
#include<cmath>
using namespace std;
struct Rt
{
    int x;
    int y;
    int dmd;
};
struct Lg
{
    int u;
    int v;
};
int distMht(int x, int y, int u, int v)
{
    return abs(x - u) + abs(y - v);
}
int main()
{
    int n, m, p, c;
    while(cin >> n >> m >> p >> c)
    {
        Lg lgArr[10];
        for(int i = 0; i < n; i++)
        {
            int u, v;
            cin >> u >> v;
            lgArr[i].u = u;
            lgArr[i].v = v;
        }
        Rt rtArr[1000];
        for(int i = 0; i < m; i++)
        {
            int x, y;
            cin >> x >> y;
            rtArr[i].x = x;
            rtArr[i].y = y
            cin >> rtArr[i].dmd;
        }
        

        for(int i = 0; i < m; i++) //rt -> lg
        {
           
            int maxProfit = 0;
            bool flag = false;
            for(int j = 0; j < n; j++)
            {
                int profit =  (p - c*distMht(rtArr[i].x,rtArr[i].y,lgArr[j].u,lgArr[j].v))*rtArr[i].dmd;
                if(profit >= maxProfit)
                {
                    flag = true;
                    maxProfit = profit;
                }
            }
            if(flag)
                sumProfit += maxProfit;
            else
                remains += rtArr[i].dmd;

        }

        cout << sumProfit << "," << remains << endl;
    }


}

---

Neoj #573 - 小普刷油漆

---

用字元陣列儲存顏色

char colors[7] = {'R', 'O', 'Y', 'G', 'B', 'I', 'V'};

---

遞迴解法

void color(char wall[], int begin, int end ,int d) 
{
    if(d > 7)
        d = d % 7;
    //如果 d 大於 7，要從 1 重新開始

    if(end - begin == 1 or end == begin) //single element
    {
        wall[begin] = colors[d-1];
        return;
    } //離開遞迴的條件
    else
    {
        // begin ----- m1 ----- m2 ----- end
        int step = (end - begin + 1)/3; //每一個區間的長度
        int m1 = begin + step; //設定 m1 的位置
        int m2 = m1 + step; //設定 m2 的位置
        
        //塗中間的油漆
        for(int i = m1; i < m2; i++)
        {
            wall[i] = colors[d - 1];
        }
        
        color(wall, begin, m1, d+1);//塗左側的油漆，d要加一
        color(wall, m2, end, d+1); //塗右側的油漆，d要加一
    }


}

---

Main Function

int main()
{
    int n, k;
    while(cin >> n >> k)
    {
        char wall[3000] = {0};
        color(wall, 0, n, k);
        for(int i = 0; i < n; i++)
        {
            cout << wall[i];
        }
        cout << endl;
    }
}

---

完整程式碼

#include<iostream>
using namespace std;
char colors[7] = {'R', 'O', 'Y', 'G', 'B', 'I', 'V'};
void color(char wall[], int begin, int end ,int d) //begin -> m1 -> m2 -> end 
{
    if(d > 7)
    {
        d = d % 7;
    }


    if(end - begin == 1 or end == begin) //single element
    {
        wall[begin] = colors[d-1];
        return;
    }
    else
    {
        int step = (end - begin + 1)/3;
        int m1 = begin + step;
        int m2 = m1 + step;
        for(int i = m1; i < m2; i++)
        {
            wall[i] = colors[d - 1];
        }
        color(wall, begin, m1, d+1);
        color(wall, m2, end, d+1);
    }


}
int main()
{
    int n, k;
    while(cin >> n >> k)
    {
        char wall[3000] = {0};
        color(wall, 0, n, k);
        for(int i = 0; i < n; i++)
        {
            cout << wall[i];
        }
        cout << endl;
    }
    
}

---