8.20 美团笔试

T1 构造交替字符

直接构造即可

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n; cin >> n;
  string a, b;
  cin >> a >> b;
  string ans;
  for (int i = 0; i < n; ++i) {
    ans += a[i];
    ans += b[i];
  }
  cout << ans << endl;
  return 0;
}

T2 找到哨岗的位置

在 nxn 的方格中，给定三个坐标，以及哨岗到这三个点的曼哈顿距离，求哨岗的位置。如果有多个满足的点，选择字典序最小的坐标。

思路：

直接暴力，遍历所有满足要求的点，然后求交集。

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()

pair<int, int> op(int x, int y, int dx, int dy, int t) {
  switch(t) {
    case 0: return make_pair(x+dx, y+dy);
    case 1: return make_pair(x-dx, y+dy);
    case 2: return make_pair(x+dx, y-dy);
    case 3: return make_pair(x-dx, y-dy);
  }
  return make_pair(1, 1);
}

int main() {
  int n; cin >> n;
  vector<int> xx(3), yy(3), dd(3);
  set<pair<int, int>> ans;
  for (int i = 0; i < 3; ++i) {
    cin >> xx[i] >> yy[i];
  }
  for (int i = 0; i < 3; ++i) cin >> dd[i];

  for (int i = 0; i < 3; ++i) {
    set<pair<int, int>> nloc;
    set<pair<int, int>> validl;
    int d = dd[i], x = xx[i], y = yy[i];
    for (int dx = 0; dx <= d; ++dx) {
      int dy = d - dx;
      for (int t = 0; t < 4; ++t) {
        pair<int, int> co = op(x, y, dx, dy, t);
        int nx = co.first, ny = co.second;
        if (nx > 0 && nx <= n && ny > 0 && ny <= n) {
          validl.emplace(nx, ny);
        }
      }
    }
    if (ans.empty()) {
      ans = move(validl);
    } else {
      set_intersection(all(ans), all(validl), inserter(nloc, nloc.begin()));
      ans = move(nloc);
    }
  }

  cout << ans.begin()->first << " " << ans.begin()->second << endl;
  return 0;
}

T3 最高效率的复习

小明要期末考试了，但是他并没有准备好，每门课都有一个分数和拿到分数的概率。小明可以选择复习 m 门课，这 m 门课的概率将会提升至 100%。

思路：

我们先求出期望分数，然后求出每门课可以提升的分数（总分 - 期望分数），然后根据提升分数排序，选择前 m 个分数即可。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> p(n), a(n);
  for (auto& e : p) cin >> e;
  for (auto& e : a) cin >> e;
  for (int i = 0; i < n; ++i) {
    p[i] *= a[i];
  }
  for (int i = 0; i < n; ++i) {
    a[i] = a[i] * 100 - p[i];
  }
  sort(a.begin(), a.end(), greater<ll>());
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    ans += p[i];
  }
  for (int i = 0; i < min(n, m); ++i) {
    ans += a[i];
  }
  double ret = (double) ans / 100.;
  cout << fixed << setprecision(2) << ret << endl;
  return 0;
}

T4 变为相同串的最小代价

把两个数组变为完全相同数组的最小代价是多少？

可以进行两种操作：

1. 选择一个数组中的元素 a，把它删去，代价为 abs(a)
2. 选择一个数组中的元素 a，把它变为 b，代价为 abs(a-b)

思路：

可以用动态规划求解，假设我们用 表示数组 A[:i] 与 B[:j] 完全相等需要的代价，那么很容易写出转移方程：
$$

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define maxn 2005

ll f[maxn][maxn];
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(m);
  for (auto& e : a) cin >> e;
  for (auto& e : b) cin >> e;
  memset(f, 0x3f, sizeof(f));
  f[0][0] = 0;
  for (int i = 1; i <= m; ++i) {
    f[0][i] = f[0][i-1] + abs(b[i-1]);
  }
  for (int j = 1; j <= n; ++j) {
    f[j][0] = f[j-1][0] + abs(a[j-1]);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        // del the a[i]
        f[i+1][j+1] = min(f[i+1][j+1], f[i][j+1] + abs(a[i]));
        // del the b[j]
        f[i+1][j+1] = min(f[i+1][j+1], f[i+1][j] + abs(b[j]));
        // del modify the a[i] to b[j]
        f[i+1][j+1] = min(f[i+1][j+1], f[i][j] + abs(a[i] - b[j]));
    }
  }
  cout << f[n][m] << endl;
  return 0;
}

T5 压住试卷的最小重量

每张试卷都需要至少 bi 的重量压住，我们有 m 中石头，每个石头的重量为 ai，那么总共需要多少重量的石头？

思路：

选择刚好可以压住试卷的最小石头

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(n);
  for (auto& e : b) cin >> e;
  for (auto& e : a) cin >> e;
  sort(a.begin(), a.end());
  int ans = 0;
  for (auto e : b) {
    auto it = lower_bound(a.begin(), a.end(), e);
    if (it == a.end()) {
      ans = -1; break;
    }
    ans += *it;
  }

  cout << ans << endl;
  return 0;
}