首页 > 腾讯8.22 后台笔试C++
头像
如困兽
编辑于 2021-08-22 22:47
+ 关注

腾讯8.22 后台笔试C++

前4题AC,最后一题用dfs超时,过了55%

1. 链表断开分组。
2. 魔法球
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

static bool cmp(int& a, int& b){
    return a > b;
}

int max_num = 1000000007;
int main(){
    int T = 0;
    cin >> T;
    while(T--){
        int n = 0;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; ++i)cin >> a[i];
        sort(a.begin(), a.end(), cmp);
        int ans = 0;
        int temp = 0;
        for(int i = 0; i < n; ++i){
            ans += a[i] + temp;
            ans %= max_num;
            temp = ans;
        }
        cout << ans << endl;
    }
    return 0;
}
3. 小船载人,小船限制载重w,最多载两人,当载两个人时,两个人的体重之和必须为偶数,载一个人则没有限制。给定n个人的体重,求所需小船最少个数。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

static bool cmp(int& a, int& b){
    return a > b;
}

int findFirstIndex(vector<int>& a, int left, int target){
    int right = a.size() - 1, ans = a.size();

    while(left <= right){
        int mid = (left + right) / 2;
        if(a[mid] == target){
            ans = mid;
            break;
        }
        else if(a[mid] < target){
            ans = mid;
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    } 

    return ans;
}

int main(){
    int T = 0;
    cin >> T;
    while(T--){
        int n = 0, w = 0;
        cin >> n >> w;
        unordered_map<int, int> maps;
        for(int i = 0; i < n; ++i){
            int temp;
            cin >> temp;
            maps[temp]++;
        }
        vector<int> a;

        for(auto it = maps.begin(); it != maps.end(); it++){
            a.emplace_back((*it).first);
        }
        sort(a.begin(), a.end(), cmp);
        int ans = 0;
        for(int i = 0; i < a.size(); ++i){
            int x = a[i];
            if(maps[x] == 0)continue;
            int max_y = w - x;
            int begin = findFirstIndex(a, i, max_y);
            maps[x]--;
            for(int j = begin; j < a.size(); ++j){
                int y = a[j];
                if((x + y) % 2 == 1 || maps[y] == 0)continue;
                maps[y]--;
                break;
            }
            ans++;
            if(maps[x] != 0)i--;
        }
        cout << ans << endl;
    }
    return 0;
}
4. 字符串长度为n,找到长为k的字典序最大子序列(可以不连续)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int dp[1001][1001] = {-1};

int main(){
    int n, k;
    cin >> n >> k;
    string str;
    cin >> str;
    if(n == k){
        cout << str << endl;
    }
    else{
        string ans = "";
        for(int i = 0; i < n; ++i){
            dp[i][i] = i;
        }

        for(int step = 1; step < n; ++step){
            for(int i = 0; i < n - step; ++i){
                int j = i + step;
                int idx = dp[i][j - 1];
                if(str[j] > str[idx]){
                    dp[i][j] = j;
                }
                else{
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        int left = -1;
        for(int i = 0; i < k; ++i){
            int right = n - k + i;
            ans.push_back(str[dp[left + 1][right]]);
            left = dp[left + 1][right];
        }
        cout << ans << endl;
    }
    return 0;
}
5. n个色块,开始任意选择一个神奇色块,值为x,包含神奇色块的及周围同一数值的色块(都为x)可以一起变为另一个值y,消耗能量abs(x - y),求将n个色块变为同一数所消耗的最小能量。
超时代码,过了55%
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int ans = 2147483647;

vector<int> a;

void dfs(int cur, int left, int right, int val){
    if(cur > ans){
        return;
    }
    if(left == 0 && right == a.size() - 1){
        ans = cur;
        return;
    }
    if(left > 0 && right < a.size() - 1 && a[left - 1] == a[right + 1]){
        int new_left = left - 1;
        int new_right = right + 1;
        int temp = abs(val - a[new_left]);
        for(int i = left - 2; i >= 0; --i){
            if(a[i] == a[new_left])new_left = i;
            else break;
        }
        for(int i = right + 2; i < a.size(); ++i){
            if(a[i] == a[new_right])new_right = i;
            else break;
        }
        dfs(cur + temp, new_left, new_right, a[new_left]);
    }
    else{
        if(left > 0){
            int new_left = left - 1;
            int temp = abs(val - a[new_left]);
            for(int i = left - 2; i >= 0; --i){
                if(a[i] == a[new_left])new_left = i;
                else break;
            }
            dfs(cur + temp, new_left, right, a[new_left]);
        }

        if(right < a.size() - 1){
            int new_right = right + 1;
            int temp = abs(val - a[new_right]);
            for(int i = right + 2; i < a.size(); ++i){
                if(a[i] == a[new_right])new_right = i;
                else break;
            }
            dfs(cur + temp, left, new_right, a[new_right]);
        }
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        int k;
        cin >> k;
        a.emplace_back(k);
    }

    for(int i = 0; i < n; ++i){
        int j = i;
        while(j < n){
            if(a[i] != a[j]){
                j--;
                break;
            }
            j++;
        }
        dfs(0, i, j, a[i]);        
        i = j;
    }
    cout << ans << endl;
    return 0;
}

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐