9.20腾讯真题总结

腾讯2018春招技术类编程题汇总

第一题：
大概题意：
翻转数组，输入n和m，n代表数组数据从[1..n],m代表每m个进行一次变号，从负号开始，输出数组前n项和
举例：
输入：8 4
数据：-1 -2 -3 -4 5 6 7 8
输出：自己算

输入：3 1
数据：-1 2 -3
输出：-2

我的思路：
遍历、相加，通过flag决定符号
结果：90%，超时

第二题：
大概题意：
2人轮流从数组里取数，每次均取最大的数，求最后2人之差
输入：n n个ai
数据：a1 a2 ... an

我的思路：
输入后直接排序，然后通过flag模拟取数，最后输出结果
结果：100%

第三题：
大概题意：
吃饼干，n天内每天都需要吃，且每天吃的数量不能少于前一天的一半，总共m块饼干，问第一天最多吃多少

输入：n m

我的思路：二分查找
先设计一个函数，第一天吃start块饼干，至少需要多少饼干
之后二分查找即可

结果：100%
代码：

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

int n,m;

//o(n)
int canEat(int start){
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=start;
     if (start >= 2){
            if (start % 2 == 0)
                start /= 2;
            else
                start = start / 2 + 1;
        }}
    return sum;
};

int main(){    
    cin>>n>>m;
    int left=1,right=m;
    int ret=1;
    while(left<=right){
        int mid=left+(right-left)/2;
        int key=canEat(mid);
        if(key<=m){
            ret=ret<mid?mid:ret;
            left=mid+1;
        }
        else
            right=mid-1;            
    }
    cout<<ret<<endl;
    return 0;
};