网易游戏技术岗在线编程题(二)

题目来源:牛客网-网易2016年研发工程师编程题二

1. 奖学金

小v今年有n门课,每门都有考试,为了拿到奖学金,小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成,满分为r。现在他知道每门课的平时成绩为ai ,若想让这门课的考试成绩多拿一分的话,小v要花bi 的时间复习,不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金,小v至少要花多少时间复习。

输入描述: 第一行三个整数n,r,avg(n大于等于1小于等于1e5,r大于等于1小于等于1e9,avg大于等于1小于等于1e6),接下来n行,每行两个整数ai和bi,均小于等于1e6大于等于1

输出描述: 一行输出答案。

输入例子: 5 10 9 0 5 9 1 8 1 0 1 9 100

输出例子: 43

分析: 完成这个题目需要注意两个问题: (1)求出最少复习时间,需要优先选择每分的复习时间最小的课程,那么需要对<平时成绩,复习时间>元素对按复习时间递增进行排序; (2)因为课程数很多,每分复习时间很大,所需最小复习时间需要长整型来存储,以防溢出; (3)如果所需复习时间小于等于0,需要特殊处理。

测试通过源码:

#include  <iostream>
#include <vector>
#include <algorithm>
using namespace std;


bool compare(const vector<int>& vec0,const vector<int>& vec1)
{
  return vec0[1]<vec1[1]; //升序排列
}

int main(int argc,char* argv[]){
    int courseNum=0,maxScore=0,average=0;
    while(cin>>courseNum>>maxScore>>average){
        vector<vector<int> > regularGrade_effort(courseNum,vector<int>(2,0));
        int regularGradeSum=0;//平时总分
        for(int i=0;i<courseNum;++i){
            cin>>regularGrade_effort[i][0]>>regularGrade_effort[i][1];
            regularGradeSum+=regularGrade_effort[i][0];
        }
        sort(regularGrade_effort.begin(),regularGrade_effort.end(),compare);//按每分的复习时间升序排列

        long long int minimumTime=0;  //因为每分的复习时间很大,需要长整型,否则溢出,不能通过测试
        int needScore=courseNum*average-regularGradeSum;
        if (needScore <=0)    
            goto end;  

        for(int i=0;i<courseNum;++i){
            for(int j=0;j<maxScore-regularGrade_effort[i][0];++j){
                --needScore;
                minimumTime+=regularGrade_effort[i][1];
                if(needScore==0)
                    goto end;
            }
        }
        end:
            cout<<minimumTime<<endl;
    }
}

2.路灯

一条长l的笔直的街道上有n个路灯,若这条街的起点为0,终点为l,第i个路灯坐标为ai,每盏灯可以覆盖到的最远距离为d,为了照明需求,所有灯的灯光必须覆盖整条街,但是为了省电,要求这个d最小,请找到这个最小的d。

输入描述: 每组数据第一行两个整数n和l(n大于0小于等于1000,l小于等于1000000000大于0)。第二行有n个整数(均大于等于0小于等于l),为每盏灯的坐标,多个路灯可以在同一点。

输出描述: 输出答案,保留两位小数。

输入例子: 7 15 15 5 3 7 9 14 0

输出例子: 2.5

分析: (1)问题的实质是求一个数组序列中的两个连续元素之间的最大差值,还需要考虑首尾的特殊性; (2)我为了练习set集合容器,所以使用了set来存储路灯位置,当然你也可以使用vector容器。相对于vector容器,其好处是元素不重复,自动排序,劣势就是迭代器不支持算术加减操作,只支持自增++和自减–操作。

测试通过的源码:

#include  <iostream>
#include <set>
#include <iomanip>
using namespace std;

int main(int argc,char* argv[]){
    int n=0,l=0;
    set<int> lampPos;  //默认升序排列
    while(cin>>n>>l){
        int pos=0;
        for(int i=0;i<n;++i){
            cin>>pos;
            lampPos.insert(pos);
        }
        int maxDistance=0;
        for(set<int>::iterator it=lampPos.begin();it!=--lampPos.end();++it){
            set<int>::iterator nextIt=++it;
            --it;
            if((*nextIt-*it)>maxDistance)
                maxDistance=*nextIt-*it;
        }
        float d=(float)maxDistance/2;
        //考虑第一个路灯到路的开始位置
        if(*lampPos.begin()>d)
            d=*lampPos.begin();
        //考虑最后一个路灯到路的结束
        if(l-*(--lampPos.end())>d)
            d=l-*(--lampPos.end());
        lampPos.clear();    
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<d<<endl;
    }
}

参考文献

[1]另一位网友实现.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【专知-关关的刷题日记15】Leetcode 27. Remove Element 方法1、2、3

题目 Given an array and a value, remove all instances of that value in place and r...

35870
来自专栏C语言C++游戏编程

C语言内置运算符丰富到令人头皮发麻,C语言基础教程之运算符篇

运算符是告诉编译器执行特定数学或逻辑函数的符号。C语言内置运算符丰富,并提供以下类型的运算符 -

14310
来自专栏用户画像

等价类方法和边界值分析方法

NextDate是一个有三个变量(月份、日期和年)的函数。函数返回输入日期后面的那个日期。变量月份、日期和年都是整数值,并满足以下条件:

10120
来自专栏编程直播室

读书笔记:《算法图解》第三章 递归

17650
来自专栏HTML5学堂

算法之旅 | 冒泡排序法

HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

42490
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

32440
来自专栏绿巨人专栏

Category Theory: 01 One Structured Family of Structures

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

14130
来自专栏算法channel

其他|二维指针,数组指针,指针数组

望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1c++ c/c++的重要性毋庸置疑,凡是对性能要求很高的系统和算法,其中核...

37950
来自专栏数据结构与算法

等差数列与等比数列

数列中的每一项都和它的序号有关,排在第一位的数称为这个数列的第一项(通常也叫做首项)

10420
来自专栏落影的专栏

程序员进阶之算法练习(十七)

前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 如何从这篇文章受益? 先看题目大意,对照Example的样...

46290

扫码关注云+社区

领取腾讯云代金券