(入門組)寒假每日一題 Week1

1月9日 AcWing 104. 貨倉選址

分析

假設有a, b商店, 那麼貨倉距離每個商店的總距離為 ∣ x − a ∣ + ∣ x − b ∣ |x - a| + |x - b| ∣x−a∣+∣x−b∣

根據絕對值不等式 ∣ x − a ∣ + ∣ x − b ∣ > = ∣ a − b ∣ |x - a| + |x - b| >= |a - b| ∣x−a∣+∣x−b∣>=∣a−b∣, 當 x x x 取到[a, b]之間的任何數, 都可以取到使得 ∣ x − a ∣ + ∣ x − b ∣ |x - a| + |x - b| ∣x−a∣+∣x−b∣取得最小值

同理對于

∣ a 1 − x ∣ + ∣ a 2 − x ∣ + . . . ∣ a n − x ∣ |a_1 - x| + |a_2 - x| + ...|a_n - x| ∣a1​−x∣+∣a2​−x∣+...∣an​−x∣

前後一對一對看,

要想使得 ∣ a 1 − x ∣ + ∣ a n − x ∣ |a_1 - x| + |a_n - x| ∣a1​−x∣+∣an​−x∣ 取得最小, 那麼 x x x需要在 [ a 1 , a n ] [a_1, a_n] [a1​,an​]範圍内,

取得 ∣ a k − x ∣ + ∣ a k + 1 − x ∣ |a_k - x| + |a_{k + 1} - x| ∣ak​−x∣+∣ak+1​−x∣範圍内, x x x必須在 [ a k , a k + 1 ] [a_k, a_{k + 1}] [ak​,ak+1​]内, k為 a 1 , a 2 , . . . , a n {a_1, a_2, ..., a_n} a1​,a2​,...,an​的中位數.

綜上,

1. 數組個數為奇數的時候, x x x取數組的中位數
2. 數組個數為偶數的時候, x x x取 [ a k , a k + 1 ] [a_k, a_{k + 1}] [ak​,ak+1​]中的任何一個數

可以取得最小值.

注意: 這裡的 a 1 , a 2 , . . . , a n {a_1, a_2, ..., a_n} a1​,a2​,...,an​是排好序的數組, 是以代碼中需要先對數組排序

code

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
int main(){
    cin >> n;
    int res = 0;
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);
    for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]);
    cout << res << endl;
    return 0;
}
           

AcWing 898. 數字三角形

分析

如果循環層數

i

從上往下dp分析, 即:

for(int i = 1; i <= n; i ++ )

,

那麼

f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]

, 需要考慮最左邊界的問題

而從下往上面

for (int i = n; i >= 1; i --)

dp, 就不需要考慮邊界問題了, 因為下面的邊界囊括上面, 是以上面的狀态不會有邊界的問題

code(自上到下)

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int a[N][N];
int n;

int main(){
    cin >> n;
    memset(a, -0x3f, sizeof a);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            cin >> a[i][j];
            
    for (int i = 1; i <= n; i ++ )   
        for (int j = 1; j <= i; j ++ )
            if (i == 1 && j == 1) a[i][j] = a[i][j];
            else if (j == 1) a[i][j] += a[i - 1][j];
            else a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]);
    int res = -1e9;
    for (int i = 1; i <= n; i ++ ) res = max(res, a[n][i]);
    cout << res << endl;
    return 0;
}
           

code(自下到上, 優化)

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int a[N][N];
int n;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            cin >> a[i][j];
            
    for (int i = n - 1; i >= 1; i --)   
        for (int j = 1; j <= i; j ++ )
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
    cout << a[1][1] << endl;
    return 0;
}