poj-1167 The Buses

考点

• 迭代加深

题解

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 2e5 + 50;
// n个巴士m条线路
int n, m, bus[70];

int valid(int a, int d) {
  for (int i = a; i < 60; i += d) {
    if (!bus[i]) return 0;
  }
  return 1;
}

struct node {
  // 序列巴士个数，序列首项，序列公差
  int cnt_, a_, d_;
  node(int cnt = 0, int a = 0, int d = 0) : cnt_(cnt), a_(a), d_(d) {}
  // 优化搜索顺序：先从巴士个数多的开始
  bool operator<(node &x) {
    return cnt_ > x.cnt_ || cnt_ == x.cnt_ && a_ < x.a_ ||
           cnt_ == x.cnt_ && a_ == x.a_ && d_ < x.d_;
  }
} s[maxn];

bool dfs(int depth, int sum, int start) {
  if (!depth) return sum == n;
  for (int i = start; i < m; ++i) {
    int a = s[i].a_, d = s[i].d_, cnt = s[i].cnt_;
    // 可行性剪枝：当前及后续所有路线都取最多车数，都达不到目标值
    if (cnt * depth + sum < n) continue;
    if (!valid(a, d)) continue;
    for (int j = a; j < 60; j += d) --bus[j];
    if (dfs(depth - 1, sum + cnt, i)) return 1;
    for (int j = a; j < 60; j += d) ++bus[j];
  }
  return 0;
}

void init() {
  // 按时间分类统计巴士数
  cin >> n;
  for (int x, i = 0; i < n; ++i) cin >> x, ++bus[x];
  // 枚举路线首项
  for (int a = 0; a < 60; ++a) {
    // 枚举路线公差，应满足两个条件
    // d > a，否则a不是首项
    // a + d < 60 ，否则无法保证路线至少两个车
    for (int d = a + 1; a + d < 60; ++d) {
      if (valid(a, d)) s[m++] = node((59 - a) / d + 1, a, d);
    }
  }
  sort(s, s + m);
}

int main() {
  init();
  int dep = 0;
  while (!dfs(dep, 0, 0)) ++dep;
  cout << dep << endl;
  return 0;
}

思路

题目明确说了路线条数不会超过17，所以采用迭代加深。

根据题意，每条路线由(路线巴士个数，首项<第一班车到达时间>，公差<时间间隔>)三元组构成。

所以先枚举出所有可能的路线，然后迭代加深选择即可。

---

枚举路线有两个限制条件：

1. 时间间隔 > 首项，否则首项就不是首项
2. 首项 + 时间间隔 < 60，否则无法保证至少线路上有两辆车

线路上的巴士数量就等于(60 - 1 - 首项) / 间隔 + 1

---

剪枝主要分两步：

搜索顺序优化：按照巴士数量降序排列，先枚举大的可以减少分支

可行性优化：因为我们是降序排列，所以当前线路的巴士数量一定大于等于后续线路的巴士数量；

如果当前巴士数量 * 后续线路数 + 之前已选的巴士数 < 总巴士数，就剪枝。