题目:约翰准备扩大他的农场,他正在考虑N块长方形的土地。每块土地的价格是它的面积。但约翰可以同时购买多快土地,这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换。如果约翰买一块3*5的地和一块5*3的地,则他需要付5*5=25。约翰希望买下所有的土地,但是他发现分组来买这些土地可以节省经费。他需要你帮助他找到最小的经费。
时间: 2023-05-28 12:04:28 浏览: 136
思路:首先将所有的土地按照面积从大到小排序,然后依次将它们分组。每次选出面积最大的土地作为一组,然后将与它有重叠的土地加入这一组。加入的土地必须满足长宽均小于等于已经选出的土地,否则就新开一组。最后计算每一组的价格,加起来就是总经费。
具体实现时,可以使用并查集来维护已经选出的土地组成的集合,每次加入新土地时就查找与之有重叠的土地所在的集合,将它们合并起来。同时,可以使用一个优先队列来维护未被选中的土地,每次从中选出面积最大的土地加入已选中的土地中。
代码:
相关问题
农夫约翰想修理牧场周围一小段篱笆。他测量了栅栏,发现他需要 N (1≤N≤20,000)块木板,每块木板都有一定的整数长度 L i (1≤L i ≤50,000) 个单位。然后他买了一块长木板,刚好能锯成 N 块木板(也就是说,它的长度是 L i 的长度之和)。农夫约翰忽略了“切痕”,即在锯切时被锯末所损失的额外长度;你也应该忽略它。 农夫约翰悲伤地意识到他没有锯木头的锯子,所以他拿着这块长木板慢悠悠地走到农夫唐的农场,礼貌地问他是否可以借一把锯子。 农夫唐,一个秘密的资本家,没有借给农夫约翰一把锯子,而是提出向农夫约翰收取每 N−1 刀的费用。切割一块木头的费用与它的长度完全相等。切一块 21 英寸长的木板要花 21 美分。 然后,农夫唐让农夫约翰决定切割木板的顺序和位置。帮助农民约翰确定他可以花最少的钱来创建N块木板。农夫约翰知道他可以在各种不同的顺序切割板,这将导致不同的费用,因为产生的中间板是不同的长度。
农夫约翰可以使用贪心算法来解决这个问题。贪心算法是一种优化算法,它旨在帮助农夫约翰以最小的费用切割木板。它做的是,每次从未切割的木板中选择长度最长的木板,并将其切割成最短的两块,直到所有的木板都被切割完毕。这样,农夫约翰就可以花最少的钱完成木板切割。
用C++代码实现:由于最近下雨,水汇集在农夫约翰田园各处,田园是一个N×M个方格表示(1 ≤n ≤100;1≤M≤100)的矩形。每一方格要么是水('W”)(大写),要么是干燥的土地(“.”)。农民约翰想找出他的田园有多少个水坑。水坑的定义是:W通过八个方向连接成的一片算作是一个水坑。 给定一个田园矩阵,即农夫约翰的田园,确定他的田园里有多少个水坑。 输入 输入的第一行是一个整数,即n和m 接下来有n行,每行有m个字符('W' 或者 '.') 输出 输出有多少个水坑
以下是C++代码实现:
```c++
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 105;
char field[MAXN][MAXN];
bool visited[MAXN][MAXN];
int n, m;
void dfs(int x, int y) {
visited[x][y] = true;
for(int dx=-1; dx<=1; dx++) {
for(int dy=-1; dy<=1; dy++) {
int nx = x + dx, ny = y + dy;
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && field[nx][ny] == 'W')
dfs(nx, ny);
}
}
}
int countPonds() {
memset(visited, false, sizeof(visited));
int cnt = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(!visited[i][j] && field[i][j] == 'W') {
cnt++;
dfs(i, j);
}
}
}
return cnt;
}
int main() {
cin >> n >> m;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin >> field[i][j];
}
}
cout << countPonds() << endl;
return 0;
}
```
在这个代码中,我们使用了深度优先搜索(DFS)来实现对水坑的搜索。我们从田园的每一个方格开始,如果该方格是水('W'),且还没有被访问过,就从该方格开始进行DFS搜索,并标记所有搜索到的方格。这样,我们就可以找出所有的水坑数量。
代码中的countPonds()函数就是实现了这个搜索算法,并返回水坑的数量。我们在主函数中,读入田园的字符矩阵,并输出搜索结果。
注意:这个算法中使用的DFS搜索是一个比较经典的算法,但是在实际应用中,可能会出现一些问题,例如:算法复杂度过高,无法处理超大规模的数据;或者算法无法处理某些特殊情况(例如:存在大规模的“孔洞”导致搜索无法进行)。这时候,我们需要考虑其他的搜索算法或者优化方法来解决这些问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)