# Week 08 - 作業講解
## Neoj #991 - Sprouty Mart
Benson Chiu @ Sprout 2022
---
### 解題思路
- 對於每一個便利商店，我們尋找一個使 ==利潤最大== 且 ==大於等於 0== 的物流中心
- 因為商品價格皆相同，利潤取決於**距離**
- 如何決定送貨量？
- 題目沒有特別指出物流中心的限制，故**送貨量即為需求量**
- 用兩個變數分別統計目前累積的銷貨毛利與未被滿足的需求
---
### 運用 Struct 進行適當的模組化
```cpp=
struct Rt
{
int x;
int y;
int dmd;
};
struct Lg
{
int u;
int v;
};
```
---
### 距離也可以用函數包起來
```cpp=
int distMht(int x, int y, int u, int v)
{
return abs(x - u) + abs(y - v);
}
```
---
### 輸入資料：以便利商店為例
```cpp=
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;
}
```
---
### 對於每一個零售店選擇一個獲利最大的物流中心
```cpp=
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 -> 存取未被滿足的需求
}
```
---
### 輸出結果
```cpp=
cout << sumProfit << "," << remains << endl;
```
---
### 完整程式碼
```cpp=
#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 - 小普刷油漆
---
### 用字元陣列儲存顏色
```cpp =
char colors[7] = {'R', 'O', 'Y', 'G', 'B', 'I', 'V'};
```
---
### 遞迴解法
``` cpp =
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
```cpp=
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;
}
}
```
---
## 完整程式碼
```cpp=
#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;
}
}
```
---
Sign in with Wallet
Connect another wallet