Re: [闲聊] 每日leetcode

楼主: oin1104 (是oin的说)   2024-07-31 13:41:14
题目翻译:
有一堆书 给你他们的宽跟高
跟一个宽shelfWidth的书架
每次放书都要照顺序垂直放进去
不可以叠在一起
放满了就放个隔板 然后去下一层放
请问最少要多少高度的书架才能装下所有书
思路:
我原本没看到要找顺序
所以就sort然后从大赛到小
干咧
```cpp
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth)
{
int n = books.size();
sort(books.begin() , books.end() , [](vector<int> &a , vector<int> &b){
return a[1]>b[1];
} );
for(int i = 0 ; i < n ; i ++)cout<<books[i][0]<<" "<<books[i][1]<<" ";
vector<int> used(n,0);
int now = 0;
int h = 0;
int nowh = 0;
int noww = 0;
while(now < n)
{
noww = 0;
nowh = -1;
for(int i = 0 ; i < n ; i ++)
{
if(used[i])continue;
if(noww + books[i][0] > shelfWidth)continue;
if(nowh == -1)nowh = books[i][1];
noww += books[i][0];
now ++;
used[i] = 1;
}
h += nowh;
}
return h;
}
};
```
思路2:
看了提示 dp
把每个书都当作是最后一本书
往前找最后一层的书跟他们原本的高度
这样就可以用dp来找所有的高度了
套路题= =
好像还有recursive 的做法
累累
```cpp
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth)
{
int n = books.size();
vector<int> paper(n+1,99999999);
paper[0]=0;
for(int i = 1 ; i <= n ; i ++)
{
int cw = books[i-1][0];
int allw = cw;
int ch = books[i-1][1];
paper[i] = paper[i-1]+ch;
for(int j = i -1 ; j > 0 ; j
作者: JIWP (JIWP)   2024-07-31 13:42:00
我好崇拜你
作者: SydLrio (狂岚嘴砲)   2024-07-31 13:46:00
你有什么用
作者: sustainer123 (caster)   2024-07-31 13:49:00
我好崇拜你

Links booklink

Contact Us: admin [ a t ] ucptt.com