携程9.19笔试ak附解答

本来秋招已经结束了就不想做了，但闲着也是闲着，4道题做完感觉难度还是很友好的

一、计算网格内走k步获取的最大价值

先走第0列再走最后一行，再有多余的步数就在最后一个点和倒数第二个点循环走就行了

#include <iostream>

using namespace std;

typedef long long ll;

int main(int argc, char const *argv[])
{
  /* code */
  int q;
  cin >> q;
  while (q--)
  {
    ll n, m, k, res;
    cin >> n >> m >> k;
    if (k <= n - 1)
    {
      res = (1 + k) * k * m / 2;
    }
    else if (k <= n + m - 2)
    {
      ll a = n * (n - 1) * m / 2;
      k -= (n - 1);
      res = a + k * (n - 1) * m + (k + 1) * k / 2;
    }
    else
    {
      res = n * (n - 1) * m / 2 + (m - 1) * (n - 1) * m + m * (m - 1) / 2;
      k -= (n + m - 2);
      res += ((k / 2) * (2 * (n - 1) * m + 2 * m - 3));
      if (k % 2)
      {
        res += ((n - 1) * m + m - 2);
      }
    }
    cout << res << endl;
  }

  return 0;
}

二、选m个极差不超过k的数消掉最小的数，求剩余最少的数字数量

排序从小到大遍历看最小的数能不能被消掉就行

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e6 + 100;

int a[maxn];
int n, m, k;

int main(int argc, char const *argv[])
{
  /* code */
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }

  int total = n;
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++)
  {
    int nxt = i + m - 1;
    if (nxt > n)
    {
      break;
    }
    if (a[nxt] - a[i] <= k)
    {
      total--;
    }
  }

  cout << total << endl;

  return 0;
}

三、选k个长度不超过l的区间改变数字，求最后剩余的最小数字

二分最小数字即可

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

const int maxn = 1e5 + 100;

int a[maxn];
int b[maxn];
int n, k, l;

bool check(int val)
{
  int last = 0;
  int cnt = 0;
  for (int i = 1; i <= n; i++)
  {
    if (a[i] < val)
    {
      if (last == 0)
      {
        last = i;
        cnt++;
      }
      else if (i - last + 1 > l)
      {
        last = i;
        cnt++;
      }
    }
  }
  return cnt <= k;
}

int main(int argc, const char **argv)
{
  cin >> n >> k >> l;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
    b[i] = a[i];
  }

  sort(b + 1, b + 1 + n);

  int lef = 1, rig = n;
  int result = -1;
  while (lef <= rig)
  {
    int mid = lef + (rig - lef) / 2;
    if (check(b[mid]))
    {
      result = mid;
      lef = mid + 1;
    }
    else
    {
      rig = mid - 1;
    }
  }
  cout << b[result] << endl;
  return 0;
}

四、求所有员工拿到通行证再到公司的最短时间

首先把通行证和员工的坐标排序，可以确定的是如果最优解中第i个员工拿了第j个通行证，那么前i-1个员工的通行证一定在前j-1个里选，这样可以用动态规划求解

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n, k, p;
int a[2010];
int b[2010];
int dp[2010][2010];

int main(int argc, char const *argv[])
{
  /* code */
  cin >> n >> k >> p;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }

  for (int i = 1; i <= k; i++)
  {
    cin >> b[i];
  }

  sort(a + 1, a + 1 + n);
  sort(b + 1, b + 1 + k);

  for (int i = 1; i <= n; i++)
  {
    dp[i][0] = INT32_MAX;
  }

  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= k; j++)
    {
      if (j < i)
      {
        dp[i][j] = INT32_MAX;
      }
      else
      {
        dp[i][j] = max(dp[i - 1][j - 1], abs(a[i] - b[j]) + abs(p - b[j]));
        dp[i][j] = min(dp[i][j], dp[i][j - 1]);
      }
    }
  }

  int res = INT32_MAX;
  for (int i = n; i <= k; i++)
  {
    res = min(res, dp[n][i]);
  }

  cout << res << endl;

  return 0;
}