2019网易实习生笔试题解

1，求区域中矩形最多重叠的个数

题目网址：https://www.nowcoder.com/test/question/done?tid=14633045&qid=152611#summary

解题思路：首先考虑暴力解，要想求得最大重叠区域，就遍历每个点最多在多少个矩形中出现，但是由于点坐标过大，肯定会超时。优化方法就是将所有矩形的横纵坐标存起来，求这些坐标组成的点最多在多少个矩形中出现，就可以了。总的时间复杂度为O（n*n*n）.

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 50 + 5;
int X1[maxn], Y1[maxn];
int X2[maxn], Y2[maxn];
set<int> xx, yy;
int a[1010],b[1010];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> X1[i];
        a[i] = X1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> Y1[i];
        b[i] = Y1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> X2[i];
        a[i+n] = X1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> Y2[i];
         b[i+n] = Y1[i];
    }
    int ans = 0;
    for(int x =0;x<2*n;x++)
    {
        for(int y=0;y<2*n ;y++)
        {
            int cnt = 0;
            for(int i = 0; i < n; i++)
            {
                if(X1[i] <= a[x] && Y1[i] <= b[y] && X2[i] > a[x] && Y2[i] > b[y]) cnt++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
    return 0;
}

 2，求数对

解题思路：首先考虑暴力解，由于数据量为10^5，时间复杂度为O(n^2)肯定会超时，优化：根据 y 来求解每个 y 有多少可能的对数量。 因为 y 小于等于 k 时，不存在大于等于 k 的余数，所以从 y=k+1 开始到 n 分别求解。接下来说明当 y 为任一值 i 时有多少对数。判断 x 在 n 中，每 i 个数中共有 i-k 个 x 取值使得条件成立，余数为k,k+1,k+2,…,i-1 共 i-k 个。所以在 n 中的前一部分总共会有((int)(n/i))*(i=k)在不能整除 i 的部分，如果 n%i<k，那么这部分不存在满足条件的对数，否则此部分的满足条件的对数为 n%i-k+1对 y 的每个值都计算上两个部分，并计数，可以在O(n)的时间内实现。特殊情况考虑，当K为0时，由于在计算n%i>=k时，不能出现余数为0 的情况，这里每次都多加了1.需要减去n。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    while(scanf("%d %d",&n,&k)!=EOF)
    {
            long long int sum = 0;
            for(int i=k+1;i<=n;i++)
            {
                int p = n/i;
                sum+=p*(i-k);
                if(n%i>=k) sum+=(n%i - k+1);
            }
            if(k==0) sum-=n;
            printf("%lld\n",sum);


    }
}

 3，找工作

解题思路：首先将小伙伴的工作能力和难度一起排序，时间复杂度为O（（n+m）*log（n+m）），然后从前往后扫一遍，需要使用map映射，

记录下标为i的小伙伴能获得的最大报酬，时间复杂度为O(n+m),总的时间复杂度为O（（n+m）*log（n+m））

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct p
{
    int x,y;
    int id;
};
int cmp(p a,p b)
{
    if(a.x==b.x)
    return a.id < b.id;
    else return a.x<b.x;
}
p a[2*maxn];
map<int,int>mp;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
      scanf("%d %d",&a[i].x,&a[i].y);
      a[i].id = 0;
    }
    for(int i=n+1;i<=m+n;i++)
    {
         scanf("%d",&a[i].x);
         a[i].y = 0;
         a[i].id = i-n;
    }
    sort(a+1,a+1+n+m,cmp);
    int maxx = 0;
    for(int i=1;i<=n+m;i++)
    {
        maxx = max(a[i].y,maxx);
        if(a[i].id!=0)
        {
            mp[a[i].id] = maxx;
        }
    }
    int s;
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",mp[i]);
    }

}