✨✨ 欢迎大家来访Srlua的博文（づ￣3￣）づ╭❤～✨✨

🌟🌟 欢迎各位亲爱的读者，感谢你们抽出宝贵的时间来阅读我的文章。

我是Srlua小谢，在这里我会分享我的知识和经验。🎥

希望在这里，我们能一起探索IT世界的奥妙，提升我们的技能。🔮

记得先点赞👍后阅读哦~ 👏👏

📘📚 所属专栏：算法与数据结构高手养成

欢迎访问我的主页：Srlua小谢 获取更多信息和资源。✨✨🌙🌙

​​​

​​

目录

算法与数据结构高手养成:朴素的贪心法(下)二分答案

例:数列分段

思路1:最优化策略

思路2:构造法

思路3:逆向思考

思路3的局限性

用二分法降低验证次数

用二分法降低验证次数:例

代码:数列分段

二分答案法的一般步骒

适用二分答案法的问题特性

不符合单调性的例子

---

算法与数据结构高手养成:朴素的贪心法(下)二分答案

二分答案——通过答 案反推，验证合法性从而确定最优解

例:数列分段

给出一个长度为 N 的正整数数列，现在要把它分成 K 段，且每一段里所有数字的和都不超过T，问T的最小值是多少?

例:2354332，分成3段

T最小的分段:[23] [54] [332]，T=9(5+4)

思路1:最优化策略

阶段:当前分割到第几段

决策:在哪个位置分割

怎么确定最优子结构?

• 最优 =最大/最小?

  ​

  如果一直选取最优，每段尽可能小，会导致分到最后剩下的太多~！

  • 最优=最接近某个值(比如“数字和:段数”)?

    ​这样也不是最优~​

    所以最优化策略还是不行

    思路2:构造法

    此题看起来很接近划分问题?

    构造法的条件:可以通过计算或者总结得出规律

    但这道题没什么规律..

    思路3:逆向思考

    已知 T，很容易验证数列是否能被分为M段，且每段和都不超过 T

    

    • 设置一个足够小的 T 作为起始值，T 可以是理想情况的下界
    • 验证对于当前的T是否可以满足条件(分成M段，每段和小于等于 T)
    • 若不满足则T=T+1，直到找到最小的满足条件的 T

      

      思路3的局限性

      

      如果数列中有个很大的数，则我们的初始T就需要一直加，需要做很多重复工作~

      

      此时我们可以使用二分法

      用二分法降低验证次数

      给答案规定一个上下界，作为二分起始区间。本题中，T的下界是(数列和÷段数)，上界是所有数字的和

      对当前区间求中值mid，并用贪心法进行验证

      如果每段和都不超过mid时，可以划分为不多于M段，则答案在左半区间;如果划分的段数大于M，或者有数字大于mid导致不能完成划分，则答案在右半区间

      用二分法降低验证次数:例

      

       

      发现18取大了，所以往左半区间继续求mid值

      

       此时，说明最优解在9-13之间

      

      此时发现它最少只能分四段了，说明最优解是11

      代码:数列分段

      

      #include
      using namespace std;
      int n, m;
      int a[100001];
      int segmentation(int ub) {
          int count = 0, res = 0;
          for (int i = 0; i < n; i++) {
              if (a[i] > ub)
                  return INT_MAX;
              if (count + a[i] <= ub)
                  count += a[i];
              else {
                  count = a[i];
                  res += 1;
                  if (res > m)
                      break;
              }
          }
          return res + 1;
      }
      int main() {
          ios::sync_with_stdio(false);
          cin.tie(NULL);
          cout.tie(NULL);
          cin >> n >> m;
          long long sum = 0;
          for (int i = 0; i < n; i++) {
              cin >> a[i];
              sum += a[i];
          }
          
          int l = sum / n, r = 1000000000;
          if (sum < r)
              r = sum;
          while (l < r) {
              int t = (l + r) / 2;
              if (segmentation(t) <= m)
                  r = t;
              else
                  l = t + 1;
          }
          cout << l << endl;
          return 0;
      }

      二分答案法的一般步骒

      1.确定解的范围，也就是进行二分的上下边界

      2.对这个解的范围进行二分查找，每一轮二分，对于当前的中值利用贪心进行验证，如果验证通过则说明解的范围需要缩小，否则需要扩大

      3.当二分结束，确定了最小/最大的通过验证的解，就是最终答案

      适用二分答案法的问题特性

      题目所求的最优解，往往是某种上下界，比如数列划分为M段后每段的和的最大值T，就是一种上界

      如果给定了一个值，可以很容易地用贪心法验证这个值是不是一个可行解

      这个值和某个用来验证合法性的条件，一定存在某种单调性关系

      不符合单调性的例子

      将题目修改为:每段都至少包含一个数字 T，求 T的最大值

      

      

      

      

      如果此时M=2，二分会先验证T=2再验证T=1，最后得到T最大是1，但实际上T最大是4

       ​​​

      希望对你有帮助！加油！

      若您认为本文内容有益，请不吝赐予赞同并订阅，以便持续接收有价值的信息。衷心感谢您的关注和支持！