SRM477 DIV2 250

发表于 分类于

简单题，赛后看了一下好多人对数组进行了排序，然后再进行枚举判断，我觉得这样并不是最好的方法，我的方法是开一个 bool 型的数组，has[i] 代表第 ii 天如果冲突，则需要改计划，这样每次对连续的 kk 天进行枚举，用 O(nk)O(nk) 的时间可以直接 check 完，每次检查 kk 子串后，判断答案，如果比现有答案小，这更新答案，最后返回即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int bestSchedule(int N, int K, vector<int> day) {
  bool has[1100] = {0};
  int sum, ret = 0x3f3f3f3f;
  int n = day.size();
  for (int i = 0; i < n; i++) {
    has[day[i]] = true;
  }
  for (int i = 1; i <= N - K + 1; i++) {
    sum = 0;
    for (int j = 0; j < K; j++) {
      if (has[i + j]) sum++;
    }
    if (sum < ret) ret = sum;
  }
  return ret;
}