网易2019实习模拟练习题

牛牛找工作

题目

为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。

输入描述

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。

输出描述:

对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。

输入例子1:

3 3
1 100
10 1000
1000000000 1001
9 10 1000000000

输出例子1:

100
1000
1001

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class work {
public:
    int di;
    int pi;
    work()
    {
        di = 0;
        pi = 0;
    }
};
class student {
public:
    int ai;
    int id;
    student()
    {
        ai = 0;
        id = 0;
    }
};
bool sortByPi(const work &w1, const work &w2)
{
    if (w1.di == w2.di)
    {
        return w1.pi > w2.pi;
    }
    else
    {
        return w1.di < w2.di;
    }
}
bool sortByAi(const student &stu1, const student &stu2)
{
    return stu1.ai < stu2.ai;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<work> vec_work(n);
    vector<student> vec_student(m);
    for (int i = 0; i < n; i++)
    {
        cin >> vec_work[i].di >> vec_work[i].pi;
    }
    sort(vec_work.begin(), vec_work.end(), sortByPi);
    for (int j = 0; j < m; j++)
    {
        cin >> vec_student[j].ai;
        vec_student[j].id = j;
    }
    sort(vec_student.begin(), vec_student.end(), sortByAi);
    int worknum = 0, ans = 0;
    int max_pi[101000];
    for (int i = 0; i < m; i++)
    {
        while (worknum < n && vec_student[i].ai >= vec_work[worknum].di)
        {
            ans = max(vec_work[worknum].pi, ans);
            worknum++;
        }
        max_pi[vec_student[i].id] = ans;
    }
    for (int i = 0; i < m; i++)
    {
        cout << max_pi[i] << endl;
    }
    return 0;
 
}

被3整除

题目：

Q得到一个神奇的数列: 1, 12, 123,…12345678910,1234567891011…。

并且小Q对于能否被3整除这个性质很感兴趣。

小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。

输入描述:

输入包括两个整数l和r(1 <= l <= r <= 1e9), 表示要求解的区间两端。

输出描述:

输出一个整数, 表示区间内能被3整除的数字个数。

输入例子1:

2 5

输出例子1:

3

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
    int l,r;
    int cnt=0;
    cin>>l>>r;
    for(int i=l;i<=r;i++){
        if(i%3!=1){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

安置路灯

题目：

小Q正在给一条长度为n的道路设计路灯安置方案。

为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用’.’表示, 不需要照亮的障碍物格子用’X’表示。

小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。

小Q希望能安置尽量少的路灯照亮所有’.’区域, 希望你能帮他计算一下最少需要多少盏路灯。

输入描述:

输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含’.’和’X’。

输出描述:

对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。

输入例子1:

2
3
.X.
11
…XX….XX

输出例子1:

1
3

代码

#include<iostream>
#include<string>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        int num=0;
        for(int i=0;i<n;++i)
        {
            if(s[i]=='.')
            {
                ++num;
                i+=2;
            }
        }
        cout<<num<<endl;
    }
}

迷路的牛牛

题目

牛牛去犇犇老师家补课，出门的时候面向北方，但是现在他迷路了。虽然他手里有一张地图，但是他需要知道自己面向哪个方向，请你帮帮他。

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示转方向的次数N(N<=1000)。
接下来的一行包含一个长度为N的字符串，由L和R组成，L表示向左转，R表示向右转。

输出描述:

输出牛牛最后面向的方向，N表示北，S表示南，E表示东，W表示西。

输入例子1:

3
LRR

输出例子1:

E

代码

#include<iostream>
using namespace std;
 
char status = 'N';
int main()
{
    int num = 0;
    cin>>num;
    string s={0};
    cin>>s;
    char ch;
    for(int i=0;i<num;i++)
    {
        ch = s[i];
        switch(ch){
            case 'L':
                if(status == 'N') {status = 'W';break;}
                if(status == 'W') {status = 'S';break;}
                if(status == 'S') {status = 'E';break;}
                if(status == 'E') {status = 'N';break;}
            case 'R':
                if(status == 'N') {status = 'E';break;}
                if(status == 'E') {status = 'S';break;}
                if(status == 'S') {status = 'W';break;}
                if(status == 'W') {status = 'N';break;}
        }
    }
    cout << status << endl;
    return 0;
}

数对

题目

牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。

但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。

代码

#include<iostream>
using namespace std;
int main()
{
    long int n,k;
    long int res=0;
    cin>>n>>k;
    int count=0;
    if(k==0)
    {
        cout<<n*n<<endl;
        return 0;
    }
    for(int y=k+1;y<=n;++y)
    {
        res+=n/y*(y-k);
        if(n%y>=k)
        {
            res+=n%y-k+1;
        }
    }
    cout<<res<<endl;
 
    return 0;
}

矩形重叠

题目

平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。

如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。

请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <limits.h>
using namespace std;
// square overlap
class Square{
public:
    int left, right, up, down;
    bool operator <(const Square &x){
        return down < x.down;
    }
};
  
bool leftto(Square a, Square b){
    return a.left < b.left;
}
  
void eraselower(vector<Square> &a, int ybound){
    int deln = 0, i = 0, n = a.size();
    while(i + deln < n){
        if(a[i].up<=ybound)
            swap(a[i], a[n-(++deln)]);
        else
            ++i;
    }
    a.erase(a.end()-deln, a.end());
}
int main(){
    int n;
    cin>>n;
    vector<Square> sqs(n), row;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].left;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].down;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].right;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].up;
    sort(sqs.begin(), sqs.end());
    int sn = 0, curdown = 0, res = 0;
    while(sn<n)
   {
        curdown = sqs[sn].down;
        while(sn<n && sqs[sn].down == curdown)
            row.push_back(sqs[sn++]);
        eraselower(row, curdown);
        sort(row.begin(), row.end(), leftto);
        vector<int> rights;
        for(Square x:row)
        {
            rights.erase(rights.begin(), upper_bound(rights.begin(), rights.end(), x.left));
            rights.insert(upper_bound(rights.begin(), rights.end(), x.right), x.right);
            if(res < rights.size()) res = rights.size();
        }
   }
   cout<<res<<endl;
}

牛牛的闹钟

题目

牛牛总是睡过头，所以他定了很多闹钟，只有在闹钟响的时候他才会醒过来并且决定起不起床。从他起床算起他需要X分钟到达教室，上课时间为当天的A时B分，请问他最晚可以什么时间起床

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含一个正整数，表示闹钟的数量N(N<=100)。
接下来的N行每行包含两个整数，表示这个闹钟响起的时间为Hi(0<=A<24)时Mi(0<=B<60)分。
接下来的一行包含一个整数，表示从起床算起他需要X(0<=X<=100)分钟到达教室。
接下来的一行包含两个整数，表示上课时间为A(0<=A<24)时B(0<=B<60)分。
数据保证至少有一个闹钟可以让牛牛及时到达教室。

输出描述:

输出两个整数表示牛牛最晚起床时间。

输入例子1:

3
5 0
6 0
7 0
59
6 59

输出例子1:

6 0

代码

#include<iostream>
using namespace std;
int main()
{
    int N;
    cin>>N;
    int get[N];
    int hi,mi,x,goclass;
    int res=0;
    for(int i=0;i<N;++i)
    {
        cin>>hi>>mi;
        get[i]=hi*60+mi;
    }
    cin>>x>>hi>>mi;
    goclass = hi * 60 + mi;
    for (int i = 0; i < N; i++)
    {
        if (get[i] + x <= goclass && get[i] > res)
            res = get[i];
    }
    cout <<res/60<<' '<<res%60;
    return 0;
}

牛牛的背包问题

题目

牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。

输入描述:

输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数vi,表示每袋零食的体积。

输出描述:

输出一个正整数, 表示牛牛一共有多少种零食放法。

输入例子1:

3 10
1 2 4

输出例子1:

8

例子说明1:

三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有222 = 8种情况。

代码

#include<iostream>
#include<algorithm>
using namespace std;
long long nums = 1;
void DFS(vector<long long>& array, int size , long long w, long long sum, int pos){
    if(sum <= w)
    {
        nums++;
        for(int i = pos + 1 ; i < size ; ++i)
        {
            DFS(array,size,w,sum+array[i],i);
        }
    }
}
int main()
{
    int n;
    long long  w;
    cin >>n >> w;
    long long total = 0;
    vector<long long > array(n,0);
    for(int i = 0 ; i != n ; ++i)
    {
        cin >> array[i];
        total += array[i];
    }
    if(total <= w)
    {
        nums = pow(2,n);
    }
    else
    {
        sort(array.begin(),array.end());
        for(int i = 0 ; i != n ; ++i)
            DFS(array, array.size(), w, array[i],i);
    }
    cout<<nums<<endl;
    return 0;
}