为什么不能用降序加贪心做“考前临时抱佛脚”

我的想法是始终选一个耗时少的脑，将目前最大值放入。
但是题解这个方法不行，有没dl解释下为什么？

但是

img

#include <iostream>
#include <vector>
#include <algorithm>
#include<cstring>
using namespace std;

typedef long long ll;
const int N = 10000;
ll n;
ll a[N][N], s[N], b[N], x[N], y[N];

bool vod(int a, int b) {
    return a > b;
}

void solve() {
    ll ans = 0;
    for (int i = 1;i <= 4;i++) {
        memset(x, 0, sizeof(x));
        memset(y, 0, sizeof(y));
        for (int j = 1;j <= s[i];j++) {
            b[j] = a[i][j];
        }
        sort(b + 1, b + s[i] + 1, vod);
        x[1] = b[1];y[1] = 0;
        for (int j = 2;j <= s[i];j++) {
            if (x[j-1] == y[j-1]){
                x[j] = x[j - 1] + b[j];y[j] = y[j - 1];
            }
            else {
                x[j] = min(x[j - 1], y[j - 1]) == x[j - 1] ? x[j - 1] + b[j] : x[j - 1];
                y[j] = min(x[j - 1], y[j - 1]) == y[j - 1] ? y[j - 1] + b[j] : y[j - 1];
            }
        }
        ans += max(x[s[i]], y[s[i]]);

    }
    cout << ans << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    for (int i = 1;i <= 4;i++) {
        cin >> s[i];
    }
    for (int i = 1;i <= 4;i++) {
        for (int j = 1;j <= s[i];j++) {
            cin >> a[i][j];
        }
    }
    solve();
    return 0;
}

很显然，用时越短，意味着脑闲置的时间越少
而两个题必须是同一科，那么就要把每一科分成AB两组，两组的用时越接近越好
用贪心算法的话，可以快速得到一个次优解，但是几乎可以肯定不是最优解
我随便举个例子：
5,4,3,3,3
很显然5,4一组，3,3,3一组，两边相等，用时9
而用贪心算法，先排序，然后按顺序塞进短的列表里面，就会把5和4分开
变成5,3一组，4,3,3一组，这样用时是10

贪心会爆
题解（luogu）

#include<bits/stdc++.h>
using namespace std;
int a[5],i,j,k,sum,t,homework[21],dp[2501];
int main(){
    for(i=1;i<=4;i++)
        cin>>a[i];
    for(i=1;i<=4;i++){
        sum=0;    
        for(j=1;j<=a[i];j++)
            {cin>>homework[j];//输入
            sum+=homework[j];}//总时间累加
        for(j=1;j<=a[i];j++)
            for(k=sum/2;k>=homework[j];k--)//只要是总和的一半
                dp[k]=max(dp[k],dp[k-homework[j]]+homework[j]);//01背包
        t+=sum-dp[sum/2];//累加为另一个脑子
        for(j=1;j<=sum/2;j++)
        dp[j]=0;//清零
    }
    cout<<t;//输出
    return 0;
}
  • 这个问题的回答你可以参考下: https://ask.csdn.net/questions/240506
  • 这篇博客你也可以参考下：钓鱼问题（贪心算法练习题，不做题干说明）
  • 除此之外, 这篇博客: 算法设计分析，分治，贪心算法，动态规划，回溯法总结。中的 动态规划： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  • 相同点 ：
    动态规划和分治算法类似，其基本思想也是将待求的解问题分解成若干个子问题，先求解子问题，然后从这些子问题得到原问题的解
    不同点 :
    与分治算法不通的是，适用于动态规划的去求解决的问题，在分解之后的子问题往往不是相互独立的。在分治算法中有些子问题已经被计算了很多次，浪费了大量的时间，而动态规划就很好的解决了这个问题，例如已经保存了子问题的答案，当再需要使用时，就可以直接调用，避免了大量的重复计算
    为了达到这个目的，可以用一个表来记录所有已经解决的子问题的答案，无论子问题是否被用到，只要计算过就填入表中，这就是动态规划的基本思想。

    动态规划算法适用于解最优化问题，通常可以按如下几个步骤

    (1) 找出最优解的性质，并刻画其结构特征
    (2) 递归地定义最优值
    (3) 以自底向上的方式计算出最优值
    (4) 根据计算最优值是的信息，构造最优解

    动态规划算法的基本要素

    1. 最优子结构性质
    2. 子问题重叠性质

    典型例子：最长公共子序列，最大字段和，0-1背包问题。

    这里有一个0-1背包个人觉得挺好理解的博客

    https://blog.csdn.net/mu399/article/details/7722810

  • 您还可以看一下 郑光华老师的性能测试核心知识解惑课程中的 你了解的性能监控工具有哪些？小节, 巩固相关知识点
  • 以下回答由chatgpt基于相关博客总结生成:

    根据参考资料中的代码和问题描述，我们可以得到以下结论：

    问题描述中提到的“考前临时抱佛脚”方法是指每次选择一个耗时较少的脑题，并将当前解答的最大值放入。然而，题解中指出这种方法是行不通的。下面我们来解释一下原因。

    根据参考资料中的归纳法，我们可以将路径交叉的情况归结为三种情况：

    1. 第1种情况：对于每一次移动i，第i次移动距离都比第i-2次移动距离更长。也就是说，路径每次都向外扩散。

    2. 第2种情况：对于每一次移动i，第i次移动的距离都比第i-2次移动距离更短。也就是说，路径每次都向内收缩。

    3. 第3种情况：对于每一次移动ij，都满足第2种情况。

    针对这三种情况，题解中的代码分情况处理。其中，第1种和第2种情况的处理是比较直接的，而第3种情况的处理稍微复杂一些。

    对于第3种情况，有以下两种情形：

    • 第3.1种情况：第j次移动距离小于第j-2次移动距离减去第j-4次移动距离的差。此时，第j+1次移动距离需要小于第j-1次移动距离才能不出现路径交叉。

    • 第3.2种情况：第j次移动距离大于等于第j-2次移动距离减去第j-4次移动距离的差，且小于等于第j-2次移动距离。此时，第j+1次移动距离需要小于第j-1次移动距离减去第j-3次移动距离的差，才能不出现路径交叉。

    综上所述，题解中的代码根据以上的判断条件进行了处理，并最终得出是否路径交叉的结论。

    所以，使用降序加贪心的方法不能解决问题，因为该方法没有考虑到路径交叉的情况，并且没有按照题解中的判断条件进行处理。