求助有无多项式复杂度解法
  • 板块学术版
  • 楼主coding_goat
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/1/22 15:27
  • 上次更新2024/1/22 18:25:49
查看原帖
求助有无多项式复杂度解法
928805
coding_goat楼主2024/1/22 15:27

给定一个长度为 nn 数组 aa。

众所周知,将 aa 进行全排列有 n!n! 种情况。

对于每一种情况,将 aa 取前缀和,得到数组 sumsum。

在给出一个长度同为 nn 的数组 bb。

问有多少种情况对于所有的 ii 都满足 bi≤sumib_i \le sum_i


求助有无多项式复杂度解法。

还是就只能 O(n!)O(n!)。(恼

2024/1/22 15:27
加载中...