笔试题练习（网易2019实习）

1.牛牛找工作

题目：

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

输入描述:

每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量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

题目分析：

    这道题跟我们之前做的滴滴的那个餐饮的笔试题一毛一样，唯一不同的是需要记录一下同学们的id。

代码：

#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;

}

2.被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>
using namespace std;
int main()
{
    int l,r;
    cin>>l>>r;
    int count=0;
    for(int i=l;i<=r;++i)
    {
        if(i%3==0 || i%3==2)
        {
            count++;
        }
    }
    cout<<count;
    return 0;
}

3.安置路灯

题目：

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

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

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

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

输入描述:

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

输出描述:

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

输入例子1: