SRM479DIV2 题解

发表于 分类于

昨晚 (可以算是今天凌晨) 的 SRM 479，题目的难度可以说不是很难，三题我都在这里简单地说下思路：

第一题：比较水的题目，从前向后加，如果总和大于 fuelfuel 了，那么跳出，对应的 ii 就是答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find(vector<int> flights, int fuel) {
  int ret = 0;
  int num;
  int n = flights.size();
  num = n;
  for (int i = 0; i < n; i++) {
    if (ret + flights[i] <= fuel)
      ret += flights[i];
    else {
      num = i;
      break;
    }
  }
  return num;
}

第二题：简单的贪心，对 teatea 和 coffeecoffee 分别计算，每次都走到最远的没有服务过的人那里，这样花时最少，用另外的数组来记录要 coffeecoffee 的旅客编号，因为要从大到小，所以 for 循环从 n−1n-1 开始，另外要对向量 teatea 进行排序，从大到小。

注意乘客服务的时间可以直接计算，倒饮品的时间也可以直接算，剩下的就是计算走的时间了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int find(int n, vector<int> tea) {
  int nTea = tea.size();
  int nCof = 0;
  int ret = 4 * n;
  int cof[1005];
  bool type[1005] = {0};
  for (int i = 0; i < nTea; i++) type[tea[i]] = true;
  for (int i = n; i > 0; i--)
    if (!type[i]) {
      cof[nCof++] = i;
    }
  if (nTea % 7)
    ret += (nTea / 7 + 1) * 47;
  else
    ret += nTea / 7 * 47;
  if (nCof % 7)
    ret += (nCof / 7 + 1) * 47;
  else
    ret += nCof / 7 * 47;
  sort(tea.begin(), tea.end(), greater<int>());
  for (int i = 0; i < nTea; i += 7) {
    ret += 2 * tea[i];
  }
  for (int i = 0; i < nCof; i += 7) {
    ret += 2 * cof[i];
  }
  return ret;
}

第三题，比较烦的题，因为 nn 是小于等于 88 的，这样，我们可以先用 dfs 构造出最后乘客的可能顺序，然后进行模拟，计算出指定序下需要的时间，当然，但这个时间超过了 boardingTimeboardingTime 的时候，是无效的，直接返回，不用计算出确切的时间，我的做法是当时间大于 boardingTime+5boardingTime+5 的时候就直接掐掉函数运行，直接 break。

另外，要用到许多辅助数组进行状态的维护，tabletable 数组用来模拟，tmptmp 数组用来保存乘客的顺序，用于 dfs。

代码比较长：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
void Set() {
  for (int i = n + 1; i <= 2 * n; i++) {
    if (tt[i] > 0) {
      tt[i]--;
      if (tt[i] == 0) {
        table[i] = 0;
        done++;
      }
    }
  }
}

int solve() {
  memset(tt, -1, sizeof(tt));
  done = 0;
  int ans = 0;
  while (done < n) {
    Set();
    ans++;
    if (ans > maxtime + 5) break;
    for (int i = 2 * n; i > 0; i--) {
      if (table[i]) {
        if (i == table[i] + n) {
          if (tt[i] < 0)
            tt[i] = 74;
          else
            continue;
        } else {
          if (table[i + 1] == 0) {
            table[i + 1] = table[i];
            table[i] = 0;
          }
        }
      }
    }
  }
  return ans - 1;
}

void dfs(int k) {
  if (k > n) {
    for (int i = n + 1; i <= 2 * n; i++) tmp[i] = 0;
    for (int i = 1; i <= 2 * n; i++) table[i] = tmp[i];
    int ans = solve();
    if (ans <= maxtime) ret++;
  } else {
    if (source[k] == -1) {
      for (int i = 1; i <= n; i++) {
        if (!use[i]) {
          use[i] = true;
          tmp[k] = i;
          dfs(k + 1);
          use[i] = false;
        }
      }
    } else {
      tmp[k] = source[k];
      dfs(k + 1);
    }
  }
}

int find(vector<int> pattern, int boardingTime) {
  n = pattern.size();
  memset(use, 0, sizeof(use));
  for (int i = 0; i < n; i++) {
    source[i + 1] = pattern[i];
    use[source[i + 1]] = true;
  }
  ret = 0;
  maxtime = boardingTime;
  dfs(1);
  return ret;
}

总结：编码能力还是可以，就是思路不是很清晰，第三题从看题到开始拍代码，花了太多时间，导致了前两题有时间优势的情况下没有把第三题 K 掉，有点可惜，接下来就是做 Division 1 了，但愿我不要在 Division 1 上出什么差错。