美团笔试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 经过评论区大佬们指正 做法还是有问题  等一个题解