腾讯2018春招技术类编程题汇总
1、题目：
小Q定义了一种数列称为翻转数列:
给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4..., 每隔m个符号翻转一次, 最初符号为'-';。
例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8.
而n = 4, m = 1, 数列就是: -1, +2, -3, + 4.
小Q现在希望你能帮他算算前n项和为多少。
输入描述:
输入包括两个整数n和m(2 <= n <= 109, 1 <= m), 并且满足n能被2m整除。
输出描述:
输出一个整数, 表示前n项和。
输入例子1:
8 2
输出例子1:
8这个题是上周腾讯模拟考的时候我遇到的原题。。。。
就是一个数学题，前n项的和就是 n/2*m ，注意有的测试用例比较大，所以把结果设置成 long long 。题目还是很简单的，代码如下：
#include<iostream>
void init(){
long long n=0,m=0;
std::cin>>n>>m;
std::cout<<n/2*m;
}
int main(){
init();
return 0;
}
2、题目：
牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。
牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。
他们的得分等于他们抽到的纸牌数字总和。
现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。
输入描述:
输入包括两行。
第一行包括一个正整数n(1 <= n <= 105),表示纸牌的数量。
第二行包括n个正整数ai(1 <= ai <= 109),表示每张纸牌上的数字。
输出描述:
输出一个整数, 表示游戏结束后牛牛得分减去羊羊得分等于多少。
输入例子1:
3
2 7 4
输出例子1:
5把输入的数组快速排序，然后依次计算即可，也不难。代码如下：
#include<iostream>
#include<vector>
#include<algorithm>
void init(){
int n=0, temp=0, answer=0;
std::cin >> n;
std::vector<int>container;
while(n--){
std::cin>>temp;
container.push_back(temp);
}
sort(container.begin(),container.end());
if(container.size()%2==0){
for(int i=container.size()-1;i>=0;i-=2){
answer=answer+container[i]-container[i-1];
}
}else{
for(int i=container.size()-1;i>0;i-=2){
answer=answer+container[i]-container[i-1];
}
answer=answer+container[0];
}
std::cout<<answer;
}
int main(){
init();
return 0;
}3、题目：
小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。
输出描述:
输出一个数表示小Q第一天最多能吃多少块巧克力。
输入例子1:
3 7
输出例子1:
4思路：要求后一天的巧克力数量不能少于前一天的二分之一。即：保证前一天的巧克力数量是后一天数量的二倍，当刚好凑满m块巧克力时，即为最优解。因此，采用二分查找法，找到第一天所能吃的巧克力数量的最优解。
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int n,m;
int getsum(int a){//第一天是a
int sum = 0;
for(int i=0;i<n;i++){
sum += a;
a = (a+1)/2;//向上取整
}
return sum;
}
int main(){
cin>>n>>m;
int low = 1,high = m,mid;//所以采用二分查找，时间复杂度到O(logn)
while(low <= high){
mid = (low+high)/2;
if(getsum(mid) == m){
cout<<mid<<endl;
return 0;
}
else if(getsum(mid) > m)
high = mid - 1;
else
low = mid + 1;
}
cout<<high<<endl;
return 0;
}
