kkksc03考前临时抱佛脚

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 $4$ 科。因此要开始刷习题集，每科都有一个习题集，分别有 $s_1,s_2,s_3,s_4$ 道题目，完成每道题目需要一些时间，可能不等（ $A_1,A_2,\ldots,A_{s_1}$ ， $B_1,B_2,\ldots,B_{s_2}$ ， $C_1,C_2,\ldots,C_{s_3}$ ， $D_1,D_2,\ldots,D_{s_4}$ ）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 $2$ 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 $5$ 行数据：第 $1$ 行，为四个正整数 $s_1,s_2,s_3,s_4$ 。

第 $2$ 行，为 $A_1,A_2,\ldots,A_{s_1}$ 共 $s_1$ 个数，表示第一科习题集每道题目所消耗的时间。

第 $3$ 行，为 $B_1,B_2,\ldots,B_{s_2}$ 共 $s_2$ 个数。

第 $4$ 行，为 $C_1,C_2,\ldots,C_{s_3}$ 共 $s_3$ 个数。

第 $5$ 行，为 $D_1,D_2,\ldots,D_{s_4}$ 共 $s_4$ 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

样例 #1

样例输入 #1

样例输出 #1

提示

$1\leq s_1,s_2,s_3,s_4\leq 20$ 。

$1\leq A_1,A_2,\ldots,A_{s_1},B_1,B_2,\ldots,B_{s_2},C_1,C_2,\ldots,C_{s_3},D_1,D_2,\ldots,D_{s_4}\leq60$ 。

作答

可行的思路探索

尝试一

一开始以为是贪心, 因为时间最短, 我们同时做好像符合交换律?

对于: (已知最短完成时间是 5)

2 4 3

[1]: 2 和 4 同时做 --> 2 + (4 - 2) 和 3 同时做 --> 2 + 2 + (3 - 2) 和 0 同时做 --> 2 + 2 + 1 == 5

[2]: 2 和 3 同时做 --> 2 + (3 - 2) 和 4 同时做 --> 2 + 1 + (4 - 1) 和 0 同时做 --> 2 + 1 + 3 == 6 为什么你这么独特?!

[3]: 4 和 3 同时做 --> 3 + (4 - 3) 和 2 同时做 --> 3 + 1 + (2 - 1) 和 0 同时做 --> 3 + 1 + 1 == 5

感觉是数学?!

如果相差比较小, 那么就OK: 就是 (x - y) 与 z, 如果始终相差为最小, 那么就是答案了吧?! 寻找一种排序, 选择的方法吗?

寻找最大的数, 然后凑?

子数拆分?

在数组 $A_i$ 中寻找, 使得 $C$ 最小?, 那么结果就是 $time = A_{max} + (-C)$ (C此时为负数, 表示没有凑齐, 当然还有 C <= 0 的情况, 那么 $time = A_{max}$ 了)

$A_{max} = A_1 + A_2 + A_3 + ... + A_n + C$ ?

寻找出数组中, 序列, 使得其 $C_1 + C_2 + ... C_n$ 最小

坏了, 写半天, 不是贪心艹

能过样例...

#include <stdio.h>
#include <iostream>
#include <list>

using namespace std;

int dp_15_02_BFS(list<int>& s)
{
    if (s.size() == 1)
        return *s.begin();
    else if (s.size() == 2)
        return max(*s.begin(), *++s.begin());
    // 至少有3个元素
    s.sort([](int a, int b) {return a > b ? true : false; });// O(NlgN)

    int res = 0;
    // 尝试将小的数组合成大的数/组合出两个大的相同值的数
    // 标判数 一起做 一号位(不变位)
    auto max_ptr = s.begin();

    auto buwei = ++s.begin(); // 二号位
    while (true)
    {
        // 尝试凑合
        auto tmp = buwei;
        auto it = ++tmp;
        if (*it - (*max_ptr - *buwei) >= 0)
        {
            // 凑合成功
            *it -= (*max_ptr - *buwei);
            res += *max_ptr;
            s.pop_front();
            s.pop_front();
            if (s.size() == 1)
                return res + *s.begin();
            else if (s.size() == 2)
                return res + max(*s.begin(), *++s.begin());
            s.sort([](int a, int b) {return a > b ? true : false; });
            max_ptr = s.begin();
            buwei = ++s.begin();
        }
        else
        {
            // 凑合失败, 吞噬 it
            *buwei += *it;
            s.erase(it);
            if (s.size() == 1)
                return res + *s.begin();
            else if (s.size() == 2)
                return res + max(*s.begin(), *++s.begin());
        }
    }
}


int main(void)
{
    long long res = 0;
    int len[4];
    for (int i = 0; i < 4; ++i)
    {
        scanf("%d", &len[i]);
    }

    for (int i = 0; i < 4; ++i)
    {
        list<int> s;
        for (int j = 0, k; j < len[i]; ++j)
        {
            scanf("%d", &k);
            s.push_back(k);
        }
        res += dp_15_02_BFS(s);
    }

    printf("%lld\n", res);
    
    return 0;
}
C++

尝试二

有了上面的尝试, 就思考到了暴力遍历 (全部组合尝试一次), 显然里面就有重叠子问题, 所以可以用动态规划.

我分析的状态:

对于新增的数字, 我们可以尝试一起做, 或者不一起做?!

题解

这个是一个时间是体积，也是价值^[注]的背包问题.

核心思想实际上就是上面尝试一抽离出来的:

保证差值最小

我们没有必要局限在左脑做第一题, 右脑做第二题这样,

实际上是要保证 左脑花费的时间 - 右脑花费的时间 为最小 即可

void dp_15_dp(void)
{
    long long res = 0;
    int len[4];
    for (int i = 0; i < 4; ++i)
    {
        scanf("%d", &len[i]);
    }

    for (int i = 0; i < 4; ++i)
    {
        vector<int> s;
        int v_max = 0;
        for (int j = 0, k; j < len[i]; ++j)
        {
            scanf("%d", &k);
            v_max += k;
            s.push_back(k);
        }
        vector<int> DP(v_max / 2 + 1);

        // 最难理解就是这里的 v_max / 2 了^[1][3]
        for (int j = 0, g = v_max / 2; j < s.size(); ++j)
        {
            for (int k = g; k > 0; --k)
            {
                if (k - s[j] >= 0)
                    DP[k] = max(DP[k], DP[k - s[j]] + s[j]);
            }
        }

          // 以及这里为什么是这样做?^[1]
        res += max(DP[v_max / 2], v_max - DP[v_max/2]);
          // [2]:也可以修改为这样: res += v_max - DP[v_max/2];
    }

    printf("%lld", res);
}
C++

注解

[注]

时间是体积, 也是价值 的背包, 其 DP[i] == i 不一定成立

而是, 当体积为 i 时, 背包的最大价值 DP[i] (DP[i] <= i)

所以, ^[3]处的内容需要注意一下, 并且可以去02[题型]01背包系统学习一下!

[1]

具体来说，我们可以将每个科目的所有题目看作是一个背包，背包的容量为总时间的一半(理论上, 这个是费时间最少的那个脑子)^[2]。我们将这个背包按照 01 背包的思想进行处理，求出当容量为总时间的一半时可以获得的最大价值（也就是最少用的时间）。这个最大价值，就表示了在当前这个脑子下，可以处理的题目所需要的最短时间。

而另一个脑子所需要的时间，就等于总时间减去当前这个脑子所需要的时间, 计算完这一科, 时间为 max(左脑费时, 右脑费时)。

[2]

为什么是费时最少的脑子?

这里 DP[k] 的状态表示的是，在处理完前 j 道题目，并且总时间不超过 k 的情况下，能够得到的最大价值（即总时间）。在本题中，我们需要求解的就是组合问题，即在所有总时间不超过 v_max/2 的情况下，能够得到的最大总时间。因此，我们可以将所有题目的时间求和得到 v_max，然后将每一科的题目分成两个组，分别处理这两个组中的题目，使得处理时间尽量相等，也即让 DP[v_max/2] 尽可能大，那么剩下的题目就交给另一个大脑来处理，所需的时间就是 v_max - DP[v_max/2]。(左脑计算时间 + 右脑计算时间 == 总时间, 是不会变少的! 注意)

[3]

为什么是总时间的一半为DP取值?

在题目中，有一个假设是“背包的容量为总时间的一半（即 t/2）”。这个假设是根据问题的要求和约束条件得出的。

首先，我们回顾一下问题的描述。问题是要求在给定的时间范围内完成尽可能多的题目，但同时还有两个限制条件：

每个科目的题目数量是固定的；
做题时需要同时使用左脑和右脑，而每道题目左脑和右脑所需的时间可能不同，但总时间是固定的。在这个问题中，我们需要找到一个最优的策略来选择做哪些题目，以最大化完成的题目数量。因为每个科目的题目数量是固定的，所以我们不能通过调整题目的数量来达到最优解。

考虑到题目要求同时使用左脑和右脑来计算两道不同科目的题目，我们可以将左脑和右脑的时间限制视为两个背包的容量。而每个科目的题目数量则可以看作背包中的物品。我们的目标是尽可能多地装入物品（题目）而不超过背包的容量（时间限制）。

为了简化问题，我们可以将总时间限制 t 平均分配给左脑和右脑，即每个脑半个总时间 t/2。这样做的理由是，如果我们将总时间的一半作为背包容量，相当于我们认为左脑和右脑的时间使用是对等的，即两者同时计算两道不同科目的题目时所需的时间是一样的。

通过平均分配总时间限制 t，我们可以将左脑和右脑的时间限制视为背包的容量，将每个科目的题目数量视为物品，然后使用动态规划等方法来解决问题，找到最优的装入策略。

因此，假设背包的容量为总时间的一半（即 t/2）是为了简化问题，并且与题目要求和约束条件相一致。这个假设使得我们可以将问题转化为一个经典的背包问题，并应用相关的算法来求解最优解。

By GPT-3.5

题目背景​

题目描述​

输入格式​

输出格式​

样例 #1​

样例输入 #1​

样例输出 #1​

提示​

作答

可行的思路探索​

尝试一​

感觉是数学?!​

尝试二​

题解

注解​

[注]​

[1]​

[2]​

[3]​