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;
}

#腾讯##笔试题目#