2019 腾讯笔试后台开发编程题

in 刷题 with 0 comment

第一题:

给定n个面额的钱币,要求携带最少数量的钱币,能够组合出1-m的任意金额。m小于$10^9$
题目: 这题第一眼是完全背包,但是考虑m的范围很大,不好用数组。我们可以用贪心的思想来解决这个问题。假设我们已经用k张钱币凑出了1-k之间的所有组合,那么再加一张钱币,可以达到的新的组合范围是什么?

显然我们希望这张钱币金额最好是k+1。因为这样我们就可以用前k张钱币随意组合出的数叠加上这个k+1面额,得到[k+1, 2k+1]的面额。左边界是前k张钱币都不取的结果。右边界是使用所有钱币的凑出的最大值。
如果这个面额超出k+1达到K,则[k+1, K-1]之间的数可能不能被满足。所以我们希望在保证新钱币面额<=k+1的前提下,尽可能大(贪心想法)

简单而言:如果组成1-n所需要的硬币数为f(n),存在一个x的硬币满足x<=n+1,那么f(n+1),f(n+2)...f(n+x)为f(n)+1。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m, n;
    int a[105];
    cin >> m >> n;
    for(int i = 1; i <=n; i++) 
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    if(a[1] != 1){
        cout << -1 << endl;
        return 0;
    }
    int sum = 0;
    int ans = 0;
    while(sum < m){
        for(int i = n; i >= 1; i--){
            if(a[i] <= sum + 1){
                sum += a[i];
                ans ++;
                break;
            }
        }
    }
    cout << ans << endl;
}

第二题

给定一个01串,相邻的两位不相同则可以消除,问最后消除得到的串的长度。(送分题,括号匹配)

#include <bits/stdc++.h>
using namespace std;

int main() {
    char ch;
    int n;
    stack<char> ans;
    while(cin >> n) {
       while(!ans.empty()) ans.pop();
       while(n --) {
            cin >> ch;
            if(ans.empty() || ans.top() == ch) {
                ans.push(ch);
            }
            else {
                ans.pop();
            }
       }
       cout << ans.size() << endl;
    }
    return 0;
}

第三题

小Q打怪兽。 依次遇见N只怪兽,每只怪兽都有武力值和贿赂需要的金币数。如果没有贿赂某只怪兽,而互动的怪兽武力值总和小于等于这只怪兽,就会被攻击。贿赂之后怪兽就会护送他。问不被攻击需要的最少金币。

题解: 这是一道典型的动态规划的题目。测试数据中,我们发现武力值的范围是$[1, 10^{12}]$, 所以不可能用武力值作为数组的维度。考虑到怪兽只有50只,每只贿赂的金币数最大为2。可以用这两个作为数组的维度。
定义: dpi 为成功通过第i只怪兽,花费金币为j的最大武力值(同样的金币花费,希望武力值越大越好),那么可以很容易得到转移式。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 50;
typedef long long LL;
LL dp[maxn+5][maxn*2+5];

int main() {
    int n;
    LL attack[maxn+5];
    int coins[maxn+5];
    while(cin >> n) {
        memset(dp, -1L, sizeof(dp));
        for(int i = 1; i <= n; ++i) {
            cin >> attack[i];
        }
        for(int i = 1; i <= n; ++i) {
            cin >> coins[i];
        }
        dp[0][0] = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= 2*n; ++j) {
                if(j >= coins[i] && dp[i-1][j-coins[i]] != -1) {
                    dp[i][j] = dp[i-1][j-coins[i]] + attack[i];
                }
                if(dp[i-1][j] >= attack[i]) {
                    dp[i][j] = max(dp[i-1][j], dp[i][j]);
                }
            }
        }
        for(int j = 1; j <= 2*n; ++j) {
            if(dp[n][j] != -1) {
                cout << j << endl;
                break;
            }
        }
    }
}
Comments are closed.