笔试题：堆积木（拼多多真题）

参考：CSDN、牛客

题目描述

有N个积木，变长为Li，每个高度为1，每个重量为Wi
要求：

1. 严格保证变长大的叠在边长小的上面
2. 每个积木只能承受自身大小7倍以内的重量，所以其上所有积木重量综合不能超过这么多
3. 问最高能搭多高的积木

测试用例

输入：
10 # 积木个数N
1 2 3 4 5 6 7 8 9 10 # 各积木边长
1 1 1 1 1 1 1 1 1 10 # 各积木重量
输出：
8 #最大高度

思路

1. 首先对所有积木按照长度、重量从小到大排序；
2. 使用动态规划，dp[i][h]记录以第i块积木为底, 高为h的积木塔的最低重量。
3. 寻找以i为底、高度为j的最低重量，需要遍历[0, … , i-1]为底、高度为j-1已求解的dp[j][h-1]，进行更新

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Block
{
int length;
int weight;
Block(): length(0), weight(0) {}
};
bool cmp(const Block &a, const Block &b)
{
if (a.length != b.length)//长度从小到大排序
{
return a.length < b.length;
}
else//长度相等的，按重量从小到大排序
{
return a.weight < b.weight;
}
}
int main()
{
int N;
int l, w;
cin >> N;
vector<Block> myBlocks(N);
for (int i = 0; i < N; i++)
{
cin >> l;
myBlocks[i].length = l;
}
for (int i = 0; i < N; i++)
{
cin >> w;
myBlocks[i].weight = w;
}
//所有积木按照长度、重量从小到大排序
sort(myBlocks.begin(), myBlocks.end(), cmp);
int maxHeight = 1;
//dp[i][h]记录以第i块积木为底, 高为h的积木塔的最低重量。
vector<vector<int>> dp(N, vector<int>(N+1, -1));
dp[0][1] = myBlocks[0].weight;
for (int i = 1; i < N; i++)
{
dp[i][1] = myBlocks[i].weight;
for (int h = 2; h <= N; h++)//寻找以i为底、高度为j的最低重量
{
//需要遍历[0, ... , i-1]为底、高度为j-1已求解的dp[j][h-1]，进行更新
for (int j = i - 1; j >= 0; j--)
{
if (dp[j][h - 1] != -1 && 7 * myBlocks[i].weight >= dp[j][h - 1]
&& (dp[i][h] == -1 || myBlocks[i].weight + dp[j][h - 1] < dp[i][h]))
{
maxHeight = max(maxHeight, h);
dp[i][h] = myBlocks[i].weight + dp[j][h - 1];
}
}
}
}
cout << maxHeight << endl;
return 0;
}

最后

以上就是温暖咖啡为你收集整理的笔试题：堆积木（拼多多真题）的全部内容，希望文章能够帮你解决笔试题：堆积木（拼多多真题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。