目录
HDU1008——Elevator
题目描述
运行代码
#include <iostream>
#include <vector>
using namespace std;
int calculate(vector<int>& requests) {
int currentFloor = 0;
int total = 0;
for (int floor : requests) {
if (floor > currentFloor) {
total+= 6 * (floor - currentFloor) + 5;
}
else if (floor < currentFloor) {
total += 4 * (currentFloor - floor) + 5;
}
else {
total += 5;
}
currentFloor = floor;
}
return total;
}
int main() {
int n;
while (cin >> n && n != 0) {
vector<int> requests(n);
for (int i = 0; i < n; ++i) {
cin >> requests[i];
}
int total = calculate(requests);
cout << total << endl;
}
return 0;
}
代码思路
函数 calculate 接收一个引用传递的整数向量
requests
,表示电梯收到的楼层请求序列。初始化变量:
currentFloor
用来记录电梯当前所在的楼层。total
用来累计总时间。
遍历请求序列:
- 对于每一个
floor
请求:- 如果
floor
大于currentFloor
,说明电梯需要向上移动,消耗的能量等于上行速度乘以楼层差再加上开门时间。 - 如果
floor
小于currentFloor
,说明电梯需要向下移动,消耗的能量等于下行速度乘以楼层差再加上开门时间。 - 如果
floor
等于currentFloor
,说明电梯停留在同一楼层,只需开门能耗。 - 更新
currentFloor
为当前请求的楼层。
- 如果
- 对于每一个
返回总能耗:函数
calculate
返回累计的总时间total
。主函数 main:
- 读取输入的整数
n
,表示楼层请求序列的长度。 - 如果
n
不为零,则创建一个大小为n
的整数向量requests
并读入楼层请求数据。 - 调用
calculate
函数计算总时间。 - 输出总时间。
- 读取输入的整数
HDU1009——FatMouse' Trade
题目描述
运行代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Room {
double beans;
double food;
double ratio;
};
bool compareRatio(Room a, Room b) {
return a.ratio > b.ratio;
}
double max(double M,vector<Room>& rooms) {
for (int i = 0; i < rooms.size(); i++) {
rooms[i].ratio = rooms[i].beans / rooms[i].food;
}
sort(rooms.begin(), rooms.end(), compareRatio);
double totalBeans = 0;
for (int i = 0; i < rooms.size() && M > 0; i++) {
if (M >= rooms[i].food) {
totalBeans += rooms[i].beans;
M -= rooms[i].food;
}
else {
totalBeans += M * rooms[i].ratio;
M = 0;
}
}
return totalBeans;
}
int main() {
double M, N;
while (cin >> M >> N && M != -1 && N != -1) {
vector<Room> rooms(N);
for (int i = 0; i < N; i++) {
cin >> rooms[i].beans >> rooms[i].food;
}
double result = max(M, rooms);
printf("%.3f\n", result);
}
return 0;
}
代码思路
计算单位成本效益:首先,我们需要计算出每个房间的单位成本效益,即每磅猫粮能换取多少磅JavaBeans。这个值可以通过
J[i] / F[i]
来计算,我们称它为ratio[i]
。排序:将所有房间按照
ratio[i]
从大到小排序。这样,我们可以优先选择单位成本效益最高的房间进行交易。贪心选择:从单位成本效益最高的房间开始,尝试用完所有M磅的猫粮。对于每个房间,如果M足够支付
F[i]
,就完全交易该房间的JavaBeans;如果不够,就用剩下的猫粮按比例交易。累计收益:在交易的过程中,累计可以获得的JavaBeans总量。
重复步骤3和4,直到M磅猫粮用完。
HDU1010——Tempter of the Bone
题目描述
运行代码
#include <iostream>
#include <cstring>
using namespace std;
int sx, sy, ex, ey; // 起点和终点坐标
int n, m; // 迷宫的行数列数
char map[10][10]; // 迷宫
int flag; // 判断成功
int d[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 }; // 下、右、上、左
// 提前计算曼哈顿距离
int Distance(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
void dfs(int x, int y, int t) {
// 排除并剪枝
if (flag == 1) return; // 成功则返回
// 使用提前计算的曼哈顿距离
int distance = Distance(x, y, ex, ey);
// 剩余时间不足以走到终点 或者 当前点与终点横纵坐标差的和 与 剩余时间之差奇偶性不同。则直接否决返回
if (t < distance || (t - distance) % 2) return;
// 时间用完,则判断是否到终点并返回
if (t == 0) {
if (x == ex && y == ey) { flag = 1; return; }
else { return; }
}
//递归四个方向
for (int i = 0; i < 4; i++) {
int nx = x + d[i][0], ny = y + d[i][1]; // 下一位置
// 排除:1 越界,2 不是'.'或不是终点
if (nx > 0 && nx <= n && ny > 0 && ny <= m && (map[nx][ny] == '.' || map[nx][ny] == 'D')) {
map[nx][ny] = 'X'; // 标记当前点走过
dfs(nx, ny, t - 1); // 时间 -1,递归下一点
map[nx][ny] = '.'; // 还原状态
}
}
return;
}
int main() {
char str[10];
int t;
while (cin>>n>>m>>t) {
if (n == 0 && m == 0 && t == 0) return 0;
for (int i = 1; i <= n; i++) {
cin>>str;
for (int j = 1; j <= m; j++) {
map[i][j] = str[j - 1];
if (map[i][j] == 'S') sx = i, sy = j;
else if (map[i][j] == 'D') ex = i, ey = j;
}
}
flag = 0;
dfs(sx, sy, t);
if (flag == 0) printf("NO\n");
else printf("YES\n");
}
return 0;
}
代码思路
迷宫由字符组成的二维数组表示,其中不同的字符代表不同的地形或标记:
'.'
表示可以通过的空地。'S'
表示起点。'D'
表示终点。'X'
用于在搜索过程中临时标记已经访问过的点。
算法的核心是使用递归的 DFS 方法来探索所有可能的路径。在搜索过程中,它会检查以下条件:
终止条件:如果已经找到了一条到达终点的路径,将全局标志
flag
设置为1
并立即停止搜索。剪枝:使用曼哈顿距离作为预估剩余步数的方法,如果剩余步数不足以到达终点,或者剩余步数与曼哈顿距离的差值的奇偶性不同(意味着无法刚好在剩余时间内到达),则直接返回,避免不必要的递归。
递归探索:对于当前位置,检查四个方向(下、右、上、左)的相邻格子。如果相邻格子在迷宫范围内,并且是可以通行的或为终点,则进行递归调用,并将剩余时间减少1。
回溯:在探索完一个方向后,需要将当前格子的状态还原(将
'X'
变回'.'
),以便于后续的搜索中再次访问。
代码中还使用了一个二维数组 map
来存储迷宫的状态,以及四个一维数组 d
来存储四个方向的偏移量。
在 main
函数中,首先读取迷宫的尺寸、时间限制以及迷宫地图本身。接着,找出起点和终点的位置,并调用 dfs
函数从起点开始搜索。根据 flag
的状态,输出 "YES" 或 "NO" 表示是否存在一条满足时间限制的路径。