3490. 说出来可能不信这是排序题

Fifnmar

太窒息了,我 dfs 老是写假……

题目它让我们求「取一些数字,和超过 $k$」。那可以想到降序排列,先取大的,一直取到超过 $k$,设此时已经考虑了 $p$ 个数字(即,已经取了 $p$ 个数字)。此时剩下的数字数量设为 $n-p$,那么对这种情况就有 $2^{n-p}$ 种取法。

现在不取第 $p$ 个数字,从第 $p+1$ 个开始取,一直取到超过 $k$。这个过程和上一段描述的一样。此时设我们已经考虑了 $p_1$ 个数字吧!即,已经取了 $p_1 - 1$ 个数字(这是因为第 $p$ 个数字不取,我们用 $(p, p_1)$ 区间里的新数字代偿了 $p$ 号数字)。此时剩下的数字量设为 $n-p_1$,那么这种情况就有 $2^{n - p_1}$ 种取法。

重复这个过程直到所有的数都被考虑~


下面是吐糟时间:

Orz,代码总是写假的我,第一次,把 dfs 写错成了枚举暴搜,复杂度 $O(2^n)$,光荣地超时了。第二次改了一下,结果返回值搞错了。第三次才终于写对……


代码:

#include "bits/stdc++.h"
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;

u32 n;
u64 k;
vector<u32> a;
u64 ans_cnt {};

constexpr auto kOverflow = numeric_limits<u64>::max(); // an arbitrary (but larger than `kThreshold`) number to indicate overflow
constexpr u64 kThreshold = 20000000;

// returns `found_answer`
bool dfs(u32 pos, u64 accum) {
  if (accum > k) { // a[pos] has not been taken into account
    u32 nums_left = n - pos;
    if (nums_left >= 25) {
      ans_cnt = kOverflow;
    } else {
      ans_cnt += (u64)1 << nums_left;
      if (ans_cnt > kThreshold) {
        ans_cnt = kOverflow;
      }
    }
    return true;
  }
  if (pos == n) { return false; }

  auto found_answer = dfs(pos + 1, accum + a[pos]);
  if (!found_answer) { return found_answer; } // if no answer even if we take everything we can, then there's no hope.
  if (ans_cnt == kOverflow) { return true; }

  // we found at least a valid answer when taken `a[pos]`. now let's try if we can also find some other answer even
  // if we do not take `a[pos]`.
  //
  // At first I wrote `return dfs(pos + 1, accum)`, which was a fault because even if this search returns `false` I
  // should return `true` since I HAVE actually found some answers. I just have not found other answers.
  dfs(pos + 1, accum);
  return true;
}

int main() {
  cin >> n >> k;

  a.resize(n);
  for (auto& i : a) {
    cin >> i;
  }

  sort(begin(a), end(a), greater<>());

  dfs(0, 0);
  if (kOverflow == ans_cnt) {
    cout << "-1\n";
  } else {
    cout << ans_cnt << '\n';
  }
}
你当前正在回复 博客/题目
存在问题!