携程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;
}

全部评论
?就这么简单的ac了
3 回复 分享
发布于 09-19 21:09 安徽
太强了,看题解恍然大悟的感觉
2 回复 分享
发布于 09-19 21:20 北京
本来最开始就准备动态规划的-证明正确性的时候又用了一个求和而不是求最大的例子,直接让我一下否了,烦死了,从而转向-二分+二分图最大匹配,只过了93,剩下的T了
点赞 回复 分享
发布于 09-19 21:15 湖北
狠人,我A了前两道然后第三题骗分20%就交卷了
点赞 回复 分享
发布于 09-19 21:29 浙江
感觉后两题和前两题不是一个档次,后两题加起来就骗了30多😅
点赞 回复 分享
发布于 09-19 21:44 辽宁
真是狠人我淦。
点赞 回复 分享
发布于 09-19 22:37 浙江
佬第四题能再详细解释一下代码吗
点赞 回复 分享
发布于 09-20 10:34 湖南
第二题我也是这么写的,但是只能过15%,可以说是一模一样了😂
点赞 回复 分享
发布于 09-20 10:50 江苏
啊那看来我携程简历又挂了
点赞 回复 分享
发布于 09-20 11:20 湖南
大佬😱
点赞 回复 分享
发布于 09-20 18:52 湖北
前俩思路都没错,Java为啥都报我超时?只能过70
点赞 回复 分享
发布于 09-21 09:57 辽宁
第三题的check函数是干什么的啊?大佬能解释一下吗?
点赞 回复 分享
发布于 09-21 14:44 上海
第四题不知道理解对不对 dp[i][j] = Math.max(dp[i - 1][j - 1], Math.abs(a[i] - b[j]) + Math.abs(p - b[j])); //保留最小化的最大值 dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]); //对于当前员工而言,每多一个通行证(遍历j)就会有一个最小化的最大值,从这些值里面留下来最小的当作答案
点赞 回复 分享
发布于 09-22 08:49 美国
牛批,大佬
点赞 回复 分享
发布于 09-22 15:45 湖南

相关推荐

09-20 10:41
已编辑
门头沟学院 C++
面试官说,他面到现在只有一个人拿了纸质简历,悲惨的是我也没拿
找到工作就狠狠玩CSGO:没要求带简历,但确实最好带,我带了之后面试官直接对着纸质简历问的,最后我还特意把简历留下来了,希望能加深一下印象
点赞 评论 收藏
分享
31 69 评论
分享
牛客网
牛客企业服务