网易笔试题

2018/08/22 23:01
阅读数 10

(1)小易有一个古老的游戏机,上面有着经典的游戏俄罗斯方块。因为它比较古老,所以规则和一般的俄罗斯方块不同。
荧幕上一共有 n 列,每次都会有一个 1 x 1 的方块随机落下,在同一列中,后落下的方块会叠在先前的方块之上,当一整行方块都被占满时,这一行会被消去,并得到1分。
有一天,小易又开了一局游戏,当玩到第 m 个方块落下时他觉得太无聊就关掉了,小易希望你告诉他这局游戏他获得的分数。

输入描述:
第一行两个数 n, m
第二行 m 个数,c1, c2, ... , cm , ci 表示第 i 个方块落在第几列
其中 1 <= n, m <= 1000, 1 <= ci <= n
输出描述:
小易这局游戏获得的分数
输入例子1:
3 9
1 1 2 2 2 3 1 2 3
输出例子1:
2

思路:我们可以记录每个位置上的个数,得分是各个位置的最小值。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> game;
    game.resize(n+1,0);
    for(int i=0;i<m;i++)
    {
        int temp;
        cin>>temp;
        game[temp]++;
    }
    int min=1000;
    for(int i=1;i<game.size();i++)
    {
        min=min<game[i]?min:game[i];
    }
    cout<<min<<endl;
    return 0;
}

(2)小易觉得高数课太无聊了,决定睡觉。不过他对课上的一些内容挺感兴趣,所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度,并以分数量化,以及他在这堂课上每分钟是否会睡着,你可以叫醒他一次,这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。 

输入描述:
第一行 n, k (1 <= n, k <= 105) ,表示这堂课持续多少分钟,以及叫醒小易一次使他能够保持清醒的时间。
第二行 n 个数,a1, a2, ... , an(1 <= ai <= 104) 表示小易对每分钟知识点的感兴趣评分。
第三行 n 个数,t1, t2, ... , tn 表示每分钟小易是否清醒, 1表示清醒。
输出描述:
小易这堂课听到的知识点的最大兴趣值。
输入例子1:
6 3
1 3 5 2 5 4
1 1 0 1 0 0
输出例子1:
16

思路:最简单的可以暴力求解,得到我在每个时刻叫醒他所获得的兴趣值,然后找到最大的。也有一种简单点的。就是我先求出一开始他所得到的兴趣值,然后我再从前往后遍历,判断在各个时刻叫醒他,与一开始的兴趣值,遍历到最后也就找到了最大的兴趣值。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> a;
    a.resize(n,0);
    vector<int> t;
    t.resize(n,0);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>t[i];
        sum+=a[i]*t[i];
    }
    int max=sum;
    for(int i=0;i<=n-k;i++)
    {
        int temp=sum;
        for(int j=0;j<k;j++)
        {
            temp+=a[i+j]*(!t[i+j]);//取相反数,代表我叫醒,这样也不会重复加上本来就醒的兴趣值
            max=max>temp?max:temp;
        }
    }
    cout<<max<<endl;
}

(3)又到了丰收的季节,恰逢小易去牛牛的果园里游玩。
牛牛常说他对整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛。
在果园里有N堆苹果,每堆苹果的数量为ai,小易希望知道从左往右数第x个苹果是属于哪一堆的。
牛牛觉得这个问题太简单,所以希望你来替他回答。

输入描述:
第一行一个数n(1 <= n <= 105)。
第二行n个数ai(1 <= ai <= 1000),表示从左往右数第i堆有多少苹果
第三行一个数m(1 <= m <= 105),表示有m次询问。
第四行m个数qi,表示小易希望知道第qi个苹果属于哪一堆。
输出描述:
m行,第i行输出第qi个苹果属于哪一堆。
输入例子1:
5
2 7 3 4 9
3
1 25 11
输出例子1:
1
5
3

思路:这道题很简单,大家都会想到直接存储每一堆的之前的苹果总数,然后就很容易找到第Q个苹果在哪堆。但是如果单纯的找,由于后面的测试用例很大,所以一次遍历的复杂度太高,在搜索的过程中我们要用到二分搜索来降低遍历的复杂度。

这里用到的lower_bound的函数,它和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的

在从小到大的排序数组中,

lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中,重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a;
    int apple=0;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        apple+=temp;
        a.push_back(apple);
    }
    int m;
    cin>>m;
    while(m--)
    {
        int t;
        cin>>t;
        int pos=lower_bound(a.begin(),a.end(),t)-a.begin()+1;
        cout<<pos<<endl;
    }
    return 0;
}

(4)

小易有一些立方体,每个立方体的边长为1,他用这些立方体搭了一些塔。现在小易定义:这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差。小易想让这些塔尽量稳定,所以他进行了如下操作:每次从某座塔上取下一块立方体,并把它放到另一座塔上。注意,小易不会把立方体放到它原本的那座塔上,因为他认为这样毫无意义。现在小易想要知道,他进行了不超过k次操作之后,不稳定值最小是多少。
思路:很明显,我们用贪心的思想,每次都从最高的往最低的移一个,直到操作次数用完,或者最高和最低相等。
这里维护一个排序的数组,而且还要存储每个塔对应的位置,可以想到用map或者set,但是由于我们的塔中存在着高度相同的可能,所以我们考虑用set。
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int> a;
    a.resize(n,0);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    set<pair<int,int> > s;
    for(int i=0;i<n;i++)
    {
        s.insert(make_pair(a[i],i));
    }
    vector<vector<int> > ans;
    while(k>0 && s.rbegin()->first-s.begin()->first>1 && s.size()>1)
    {
        set<pair<int,int> >::iterator f1=s.begin();
        set<pair<int,int> >::reverse_iterator f2=s.rbegin();
        pair<int,int> a = *f1;
        pair<int,int> b = *f2;
        s.erase(a);
        s.erase(b);
        a.first++;
        b.first--;
        vector<int> temp;
        temp.push_back(b.second+1);
        temp.push_back(a.second+1);
        ans.push_back(temp);
        k--;
        s.insert(a);
        s.insert(b);
    }
    cout<<(*s.rbegin()).first-(*s.begin()).first<<' ';
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
        {
            cout<<ans[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部