(入门组)寒假每日一题 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;
}