美团笔试8.17

  • 1. 预处理每个数的最小质因子,若没有最小质因子则为质数输出本身,否则输出最小质因子。
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int ans[N];
void solve()
{
  for (int i = 3; i <= 1e5; i++)
  {
    for (int j = 3; j * j <= i; j++)
    {
      if (i % j == 0)
      {
        ans[i] = j;
        break;
      }
    }
  }
}
int main()
{
  solve();
  int t;
  cin >> t;
  while (t--)
  {
    int x;
    cin >> x;
    if (x & 1)
    {
      cout << (ans[x] ? ans[x] : x) << endl;
    }
    else
    {
      cout << 2 << endl;
    }
  }
}
// 64 位输出请用 printf("%lld")
  • 2. 由于数组总和不变,要让极差最小,最后极差必然是1,最后有sum%n个x+1和n-(sum%n)个x,按大小顺序依次赋值即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
int a[N];
signed main()
{
  int s = 0;
  int n;
  cin >> n;
  map<int, int> mp;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
    s += a[i];
    mp[a[i]]++;
  }
  int val = s / n;
  int y = s % n;
  int x = n - y;
  // cout<<x<<" "<<y<<endl;
  sort(a + 1, a + 1 + n);
  int m1 = 0, m2 = 0;
  for (int i = 1; i <= n; i++)
  {
    if (i <= x)
    {
      if (a[i] >= val)
        m1 += a[i] - val;
      else
        m2 += val - a[i];
    }
    else
    {
      if (a[i] >= val + 1)
        m1 += a[i] - val - 1;
      else
        m2 += val + 1 - a[i];
    }
  }
  cout << min(m1, m2);
}
  • 重点是先手要怎么乘,使得后手不会占到便宜,后手肯定选子序列最小/最大的区间,这里太菜了没想明白,感觉是dp,求大佬解答

upd:问了大佬指点会做了,实习两个月整个人都变菜了

由于先手不会让后手占便宜,选的区间肯定不会让后手也能够拿来用更优,所以两个人选的区间没交集。先预处理pre_max[i]表示到i前缀的子序列最大值,pre_min[i]表示1-i前缀的子序列最小值,后缀同理,枚举先手选的区间[i,j],后手选的是[1,i-1]的最小/最大 和 [j+1,n]的最小/最大,两者取min/max 取最小或最大由k的正负性决定

upd 经过评论区大佬们指正 做法还是有问题  等一个题解

#实习##笔试##秋招##美团#
全部评论
不用啊,第2题先求平均数,然后四舍五入。大于平均数的差值统计为num1,小于平均数的差值统计为num2,然后返回他俩的最小值就行了
4 回复 分享
发布于 08-17 20:35 江苏
感谢分享题目
3 回复 分享
发布于 08-17 21:38 黑龙江
第一题说是输出其中一个正确的就行,但是一提交就是10-
1 回复 分享
发布于 08-17 21:06 陕西
你好,第三题 -100000 1 -100000,k=2,先手选区间[2,2]乘2,后手选区间[1,3]乘2,这样不是有交集么。还是我理解有问题?
1 回复 分享
发布于 08-18 00:08 湖南
大佬第二题没看懂,能再讲讲不
点赞 回复 分享
发布于 08-17 20:36 江苏
话说考试还没结束,还有人没交卷就把答案发出来真的没问题吗
点赞 回复 分享
发布于 08-17 20:53 辽宁
我觉得先手在k小于0时需要考虑后手,需要将总和趋近于0
点赞 回复 分享
发布于 08-17 22:00 北京
t3有说两个区间不能相交吗
点赞 回复 分享
发布于 08-17 23:52 浙江
第三题,没看懂。有大佬指点一下吗?
点赞 回复 分享
发布于 08-18 00:00 北京
第三题可以看看我置顶,但是应该不是正解
点赞 回复 分享
发布于 08-18 11:34 北京
第三题区间dp,ak了
点赞 回复 分享
发布于 08-18 16:02 陕西
原数组相邻正负的数直接合并的话,最后数组只会是正负正负正负,那么第一个人枚举的点肯定是两个正,那直接枚举第一个人的范围的话,差不读是500*500/2,对这个区间的起点到整个数组的最后直接暴力处理一下,前半部分可以预处理出来,感觉卡卡能过?不知道对不对
点赞 回复 分享
发布于 08-18 20:33 广东

相关推荐

10-09 16:56
已编辑
辽宁师范大学附属中学 Java
点赞 评论 收藏
分享
10-28 20:53
已编辑
山东青客网络_CEO
比如:简历里有一句&nbsp;“使用持久化存储去解决首屏加载和用户体验问题。”【描述背景】在xxxx这个项目里,业务希望首屏加载更快,我去做了一个让首屏加载更快的方案。【描述行动】接到这个任务以后我在网上进行调研,一开始接到了集中方法,第一种是使用服务端渲染第二种使用骨架图的方案第一种服务端渲染需要服务端来跟进支持,还需要用到特殊的技术方案(这里要准备好调研的技术方案,面试官问的时候别傻了),目前这个优化只分配了前端进行改造,所以没有使用。第二种方案使用骨架图可以让页面先显示框架,再慢慢渲染实际内容,这样虽然用户感受会好一些,但是治标不治本,渲染总时长和以前是一样的。经过我的调研,我们项目首屏加载速度慢的只要原因是两个,一是JS解析执行的时间,二是React(vue)渲染的时间,然后我们的项目首页的数据不需要非常的实时精确的更新,所以我想到一个方案。【提出解决方案】每次渲染完首页后,我将首页所有的HTML代码存储到LocalStorage中,当页面进来的时候,我首先从LocalStorage中获取HTML代码数据先贴到HTML中,让用户可以先看到首页的内容和行动点,这样解决用户第一次进来速度慢的问题。【提出遇到的问题】解决这个问题需要考虑几个点:第一是读取LocalStorage插入HTML的这个代码要在所有代码之前运行第二是确保LocalStorage的存储内容的大小不能超过浏览器的限制第三是要确保HTML加载进来的时候样式也要存在【给出解决方案】我们使用的框架是UMI,使用umi的配置中的&nbsp;scripts&nbsp;参数,添加额外的JS代码,来解决第一个问题。(不同脚手架方法不一样)我们只将首屏最核心的xxxxx部分进行了代码存储,这部分的代码结构我们进行了精简,确保在100k以内。我们把这部分代码的css写成了行内样式,确保这些样式正确渲染。如果大家想要用以上内容作为简历和面试内容,我建议大家自己实践一下,做一遍这样的功能。你会发现更多值得一提的点。
点赞 评论 收藏
分享
13 28 评论
分享
牛客网
牛客企业服务