4.7晚腾讯笔试编程题解答
Problem1： 每一***作要么都减1，要么把一个数拆分为两数之和，计算所需轮数
#include <iostream>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
int main ()
{
int n, k;
while( cin >> n >>k )
{
multiset<int, greater<int> > s; //按照降序排列
s.insert(n);
int splitLayer = 0, num = 0;
//cout << *s.begin() << endl;
for(int i= 0; i < k; ++i )
{
num += pow(2, i);
if( num >= k)
{
splitLayer = i + 1;
break;
}
}
while(k--)
{
int tmp = *s.begin();
s.erase( s.begin() );
s.insert( tmp / 2 );
s.insert( tmp - tmp / 2 );
}
int great = *s.begin();
int ans = splitLayer + great;
cout << ans << endl;
}
system("pause");
return 0;
}
Problem2: 输入数组，包含正负数，求使得所有数为0时需要移动的步数
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main ()
{
int n; //村庄的数量
cin >> n;
vector<int> vec(n);
for( int i=0; i < n; ++i)
cin >> vec[i];
//cout << *vec.begin() << endl;
int p1, p2; //p1 指向第一个负数 p2指向第一个正数
int res = 0;
bool needMove = true;
while( needMove )
{
needMove = false; //注意这里是修改全局变量
for(int i=0; i < n; ++i)
{
if(vec[i] < 0)
{
p1 = i; needMove = true;
}
if(vec[i] > 0)
{
p2 = i; needMove = true;
}
}
if( abs(vec[p1]) >= abs(vec[p2]) ) // 如果负数的绝对值大
{
res += abs( vec[p2] ) * abs( p1 - p2 );
vec[p1] = vec[p1] + vec[p2];
vec[p2] = 0;
}
else
{
res += abs( vec[p1] ) * abs( p1 - p2 );
vec[p2] = vec[p1] + vec[p2];
vec[p1] = 0;
}
}
cout << "you need move:" << res << endl;
return 0;
}
Problem3: 一个数组每次输出最小的，然后其他数减去这个最小数，重复K次
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main ()
{
int n, k;
cin >> n >> k;
vector<long long> arr(n);
for(int i=0; i<n; ++i)
{
cin >> arr[i];
}
int i=0, j=0;
cout << endl << "the expected output:" << endl;
while(k--)
{
sort(arr.begin() + i, arr.end()); //降序
long long tmp = arr[i];
cout << tmp << endl;
i++;
for( j = i; j < n; ++j )
{
arr[j] -= tmp;
}
}
return 0;
}
#腾讯##笔试题目#
