AcWing寒假每日一题总结(一)

寒假已经开始很长一段时间了，隔了这么久终于有心情开始做总结了…（虽然也应该要做做总结了）。方便自己以后的整理复习和知识归纳，acwing的题目整体难度不大，也算是给自己巩固一下基础吧。

104. 货仓选址

原题链接

在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数N。
第二行N个整数A1~AN。

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

1≤N≤100000,
0≤Ai≤40000

输入样例：

4
6 2 9 1

输出样例：

12

CODE

本题考查的是中位数的知识——中位数的特点。除了题下的方法，还可以使用快速选择排序（ nth_element( )函数 ）直接找到中位数，速度会更快。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, c, len;
    long long sum = 0;
    vector<int> n;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &c);
        n.push_back(c);
    }
    sort(n.begin(), n.end());
    len = n.size();
    int mid = len / 2;
    if (len % 2) {
        for (int i = 0; i < N; i++)
            sum += abs(n[i] - n[mid]);
    } else {
        for (int i = 0; i < N; i++)
            sum += abs(n[i] - (n[mid] + n[mid - 1]) / 2);
    }
    printf("%d\n", sum);
    return 0;
}

898. 数字三角形

原题链接

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数n，表示数字三角形的层数。
接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤500,
−10000≤三角形中的整数≤10000

输入样例：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例：

30

CODE

这是一个非常经典的题目，考察内容是递推dp，我也做过很多遍了，每一次的代码都不太一样，也因为自己不太喜欢加注释的习惯导致的。这道题在经过dp之后可以只需要消耗 n * n 的空间。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m[510][510];
    memset(m, 0, sizeof m);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &m[i][j]);
    for (int i = n - 1; i; i--) {
        for (int j = 1; j <= i; j++) {
            if (m[i + 1][j] >= m[i + 1][j + 1])
                m[i][j] += m[i + 1][j];
            else
                m[i][j] += m[i + 1][j + 1];
        }
    }
    printf("%d\n", m[1][1]);
    return 0;
}