#P3285. 第4题-小美的激光打印机
-
1000ms
Tried: 15
Accepted: 3
Difficulty: 10
所属公司 :
美团
时间 :2025年5月31日-算法岗
-
算法标签>动态规划
第4题-小美的激光打印机
题解
题目描述
小美在平面上画了 n 个封闭图形,每个图形由若干点描述。激光打印机需要按顺序打印这些图形,打印每个图形时需移动激光发射器到该图形的一个点,并以特定速度绘制。所有图形打印完毕后需返回初始点。求完成所有打印的最短时间。
解题思路
- 计算周长:每个图形的周长由输入点按顺序连接形成闭合路径的长度决定。
- 枚举排列顺序:所有可能的图形打印顺序,共 n! 种情况。
- 动态规划:对每个排列顺序,通过动态规划确定每个图形的最佳起始点,使得移动时间总和最小。
- 计算总时间:包括各图形的绘制时间、图形间移动时间和返回初始点的时间。
关键点
- 周长计算:按输入点顺序计算闭合路径的总长度。
- 动态规划状态:记录当前处理到第几个图形、当前图形的起始点和初始图形的起始点。
- 时间计算:总时间为绘制时间加上移动时间,其中移动时间通过动态规划优化。
代码实现
C++
#include <bits/stdc++.h>
using namespace std;
// 定义点结构体
struct Point {
int x, y;
Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
// 重载小于运算符,用于排序
bool operator<(const Point& other) const {
if (x != other.x) return x < other.x;
return y < other.y;
}
};
// 定义图形结构体
struct Graph {
double time; // 绘制该图形所需时间
vector<Point> points; // 图形的所有顶点
};
int main() {
int n, x;
cin >> n >> x; // 输入图形数量n和移动速度x
vector<int> y(n); // 存储每个图形的打印速度
for (int i = 0; i < n; ++i) cin >> y[i];
vector<Graph> graphs(n); // 存储所有图形信息
// 处理每个图形的输入
for (int i = 0; i < n; ++i) {
int m;
cin >> m; // 当前图形的顶点数
vector<Point> points; // 存储当前图形的顶点
// 输入所有顶点坐标
for (int j = 0; j < m; ++j) {
int a, b;
cin >> a >> b;
points.emplace_back(a, b);
}
// 计算图形的周长
double perimeter = 0.0;
for (int j = 0; j < m; ++j) {
const Point& p1 = points[j];
const Point& p2 = points[(j+1) % m]; // 循环连接首尾
double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
perimeter += sqrt(dx*dx + dy*dy); // 计算两点间距离
}
// 存储图形信息
graphs[i].time = perimeter / y[i]; // 绘制时间=周长/打印速度
graphs[i].points = points;
}
vector<int> order(n); // 存储图形处理顺序
iota(order.begin(), order.end(), 0); // 初始顺序0,1,...,n-1
double min_total = 1e18; // 初始化最小总时间为极大值
// 枚举所有可能的图形处理顺序
do {
// dp_prev记录状态:(当前点,初始点) -> 累计时间
map<pair<Point, Point>, double> dp_prev;
// 初始化第一个图形的所有可能起点
const auto& first_graph = graphs[order[0]];
for (const Point& p : first_graph.points) {
dp_prev[{p, p}] = 0.0; // 从p点开始,初始移动时间为0
}
// 处理后续图形
for (int k = 1; k < n; ++k) {
const auto& curr_graph = graphs[order[k]];
map<pair<Point, Point>, double> dp_curr; // 当前状态
// 遍历前一状态
for (const auto& entry : dp_prev) {
const Point& prev_p = entry.first.first; // 前一个图形的终点
const Point& first_p = entry.first.second; // 初始点
double prev_time = entry.second; // 累计时间
// 尝试当前图形的所有可能起点
for (const Point& new_p : curr_graph.points) {
// 计算移动时间
double dx = prev_p.x - new_p.x;
double dy = prev_p.y - new_p.y;
double dist = sqrt(dx*dx + dy*dy);
double move_time = dist / x; // 移动时间=距离/移动速度
// 更新状态
auto key = make_pair(new_p, first_p);
if (!dp_curr.count(key) || prev_time + move_time < dp_curr[key]) {
dp_curr[key] = prev_time + move_time;
}
}
}
dp_prev = dp_curr;
if (dp_prev.empty()) break; // 无可行路径则跳过
}
if (dp_prev.empty()) continue; // 无解情况
// 计算返回初始点的时间
double min_move = 1e18;
for (const auto& entry : dp_prev) {
const Point& last_p = entry.first.first; // 最后一个图形的终点
const Point& first_p = entry.first.second; // 初始点
double dx = last_p.x - first_p.x;
double dy = last_p.y - first_p.y;
double dist = sqrt(dx*dx + dy*dy);
double total_move = entry.second + dist / x; // 总移动时间
if (total_move < min_move) {
min_move = total_move;
}
}
// 计算总时间:移动时间 + 所有图形绘制时间
double total_time = min_move;
for (int i : order) {
total_time += graphs[i].time;
}
// 更新最小总时间
if (total_time < min_total) {
min_total = total_time;
}
} while (next_permutation(order.begin(), order.end())); // 尝试所有排列顺序
// 输出结果,保留12位小数
cout << fixed << setprecision(12) << min_total << endl;
return 0;
}
Python
import itertools
import math
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
# 定义哈希函数,用于作为字典键
def __hash__(self):
return hash((self.x, self.y))
# 定义相等比较
def __eq__(self, other):
return self.x == other.x and self.y == other.y
# 定义小于比较,用于排序
def __lt__(self, other):
if self.x != other.x:
return self.x < other.x
return self.y < other.y
def main():
import sys
input = sys.stdin.read().split()
ptr = 0
n = int(input[ptr])
x = int(input[ptr+1])
ptr += 2
y = list(map(int, input[ptr:ptr+n]))
ptr += n
graphs = []
# 读取每个图形的数据
for i in range(n):
m = int(input[ptr])
ptr += 1
points = []
for j in range(m):
a = int(input[ptr])
b = int(input[ptr+1])
ptr += 2
points.append(Point(a, b))
# 计算周长
perimeter = 0.0
for j in range(m):
p1 = points[j]
p2 = points[(j+1)%m] # 循环连接首尾
dx = p1.x - p2.x
dy = p1.y - p2.y
perimeter += math.hypot(dx, dy) # 计算两点间距离
# 存储图形信息
time_i = perimeter / y[i] # 绘制时间=周长/打印速度
graphs.append({'time': time_i, 'points': points})
min_total = float('inf')
# 尝试所有可能的图形处理顺序
for order in itertools.permutations(range(n)):
first_points = graphs[order[0]]['points']
dp_prev = {}
# 初始化第一个图形的所有可能起点
for p in first_points:
key = (p, p)
dp_prev[key] = 0.0 # 从p点开始,初始移动时间为0
# 处理后续图形
for k in range(1, n):
curr_graph = graphs[order[k]]
curr_points = curr_graph['points']
dp_curr = {}
# 遍历前一状态
for (prev_p, first_p) in dp_prev:
prev_time = dp_prev[(prev_p, first_p)]
# 尝试当前图形的所有可能起点
for new_p in curr_points:
dx = prev_p.x - new_p.x
dy = prev_p.y - new_p.y
dist = math.hypot(dx, dy)
move_time = dist / x # 移动时间=距离/移动速度
# 更新状态
key = (new_p, first_p)
total_time = prev_time + move_time
if key not in dp_curr or total_time < dp_curr.get(key, float('inf')):
dp_curr[key] = total_time
dp_prev = dp_curr
if not dp_prev:
break # 无可行路径则跳过
if not dp_prev:
continue # 无解情况
# 计算返回初始点的时间
min_move = float('inf')
for (last_p, first_p) in dp_prev:
dx = last_p.x - first_p.x
dy = last_p.y - first_p.y
dist = math.hypot(dx, dy)
total_move = dp_prev[(last_p, first_p)] + dist / x # 总移动时间
if total_move < min_move:
min_move = total_move
# 计算总时间:移动时间 + 所有图形绘制时间
total_time = sum(graphs[i]['time'] for i in order) + min_move
# 更新最小总时间
if total_time < min_total:
min_total = total_time
# 输出结果,保留12位小数
print("{0:.12f}".format(min_total))
if __name__ == "__main__":
main()
Java
import java.util.*;
import java.awt.Point;
class Graph {
double time; // 绘制该图形所需时间
List<Point> points; // 图形的所有顶点
Graph(double time, List<Point> points) {
this.time = time;
this.points = points;
}
}
public class Main {
// 定义状态键类,包含当前点和初始点
static class Pair {
Point a;
Point b;
Pair(Point a, Point b) {
this.a = a;
this.b = b;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Pair pair = (Pair) o;
return a.equals(pair.a) && b.equals(pair.b);
}
@Override
public int hashCode() {
return Objects.hash(a, b);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 图形数量
int x = sc.nextInt(); // 移动速度
int[] y = new int[n]; // 每个图形的打印速度
for (int i = 0; i < n; i++) y[i] = sc.nextInt();
List<Graph> graphs = new ArrayList<>(); // 存储所有图形信息
// 读取每个图形的数据
for (int i = 0; i < n; i++) {
int m = sc.nextInt(); // 当前图形的顶点数
List<Point> points = new ArrayList<>();
for (int j = 0; j < m; j++) {
int a = sc.nextInt();
int b = sc.nextInt();
points.add(new Point(a, b));
}
// 计算周长
double perimeter = 0.0;
for (int j = 0; j < m; j++) {
Point p1 = points.get(j);
Point p2 = points.get((j + 1) % m); // 循环连接首尾
double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
perimeter += Math.sqrt(dx * dx + dy * dy); // 计算两点间距离
}
// 存储图形信息
graphs.add(new Graph(perimeter / y[i], points));
}
List<Integer> order = new ArrayList<>();
for (int i = 0; i < n; i++) order.add(i);
double minTotal = Double.MAX_VALUE;
// 生成所有排列顺序
do {
Map<Pair, Double> dpPrev = new HashMap<>();
List<Point> firstPoints = graphs.get(order.get(0)).points;
// 初始化第一个图形的所有可能起点
for (Point p : firstPoints) {
Pair key = new Pair(p, p);
dpPrev.put(key, 0.0); // 从p点开始,初始移动时间为0
}
// 处理后续图形
for (int k = 1; k < n; k++) {
Graph currGraph = graphs.get(order.get(k));
List<Point> currPoints = currGraph.points;
Map<Pair, Double> dpCurr = new HashMap<>();
// 遍历前一状态
for (Map.Entry<Pair, Double> entry : dpPrev.entrySet()) {
Point prevP = entry.getKey().a; // 前一个图形的终点
Point firstP = entry.getKey().b; // 初始点
double prevTime = entry.getValue();
// 尝试当前图形的所有可能起点
for (Point newP : currPoints) {
double dx = prevP.x - newP.x;
double dy = prevP.y - newP.y;
double dist = Math.sqrt(dx * dx + dy * dy);
double moveTime = dist / x; // 移动时间=距离/移动速度
// 更新状态
Pair key = new Pair(newP, firstP);
double totalTime = prevTime + moveTime;
if (!dpCurr.containsKey(key) || totalTime < dpCurr.get(key)) {
dpCurr.put(key, totalTime);
}
}
}
dpPrev = dpCurr;
if (dpPrev.isEmpty()) break; // 无可行路径则跳过
}
if (dpPrev.isEmpty()) continue; // 无解情况
// 计算返回初始点的时间
double minMove = Double.MAX_VALUE;
for (Map.Entry<Pair, Double> entry : dpPrev.entrySet()) {
Point lastP = entry.getKey().a; // 最后一个图形的终点
Point firstP = entry.getKey().b; // 初始点
double dx = lastP.x - firstP.x;
double dy = lastP.y - firstP.y;
double dist = Math.sqrt(dx * dx + dy * dy);
double totalMove = entry.getValue() + dist / x; // 总移动时间
if (totalMove < minMove) {
minMove = totalMove;
}
}
// 计算总时间:移动时间 + 所有图形绘制时间
double totalTime = minMove;
for (int i : order) {
totalTime += graphs.get(i).time;
}
// 更新最小总时间
if (totalTime < minTotal) {
minTotal = totalTime;
}
} while (nextPermutation(order)); // 尝试所有排列顺序
// 输出结果,保留12位小数
System.out.printf("%.12f\n", minTotal);
}
// 生成下一个排列
static boolean nextPermutation(List<Integer> a) {
int i = a.size() - 2;
while (i >= 0 && a.get(i) >= a.get(i + 1)) i--;
if (i < 0) return false;
int j = a.size() - 1;
while (a.get(j) <= a.get(i)) j--;
Collections.swap(a, i, j);
Collections.reverse(a.subList(i + 1, a.size()));
return true;
}
}
题目内容
小美在纸上面了 n 个封闭图形,编号为 1,2,...,n,第 i 个图形由 mi 个点描述,他正在捣鼓他的激光打印机打印出这些图形。
这个打印机可以在平面上连续的移动打印,依靠激光发射器实现,激光发射器初始可以位于平面上的任意一个点 S0 ,随后,由你确定打印顺序,按以下步骤依次打印这 n 个图形:
-
记当前打印的图形编号为 i
-
将激光发射器以 x 个单位长度每秒的速度移动到 mi 点中的其中一个(任选),作为起始端点 Si ;
-
将激光发射器以 yi 个单位长度每秒的速度任意的在纸上移动,直到经过全部 mi 个点后回到起始端点 Si ;
-
打印过程中不能暂停;若经过非当前图形的点,忽略不计;
特别的,如果全部图像打印完毕,则将激光发射器以 x 个单位长度每秒的速度移动到起始选择的点S0 ,完成打印。
直接输出整个打印过程需要的最少时间。特别的,如果图形存在重叠,你需要重复打印重叠的部分。
输入描述
第一行输入两个整数 n,x(3≦n≤7;1≦x≦1000) 代表图形数量,不打印时激光发射器的移动速度。
第二行输入 n 个整数y1,y2,...,yn(1≦yi≦1000) 代表激光发射器打印第 i 个图形的移动速度。
此后,对于第 i 个封闭图形,描述如下:
第一行输入一个整数 mi(3≦mi≦7) 代构成该图形的点的数量。
此后 mi 行,每行输入两个整数 a,b(−1000≦a,b≦1000) 代表点 (a,b) 。保证同一个图形中没有重复的点。
输出描述
输出一个整数,代表最少时间。由于实数的计算存在误差,当误差的量级不超过 10−6 时,您的答案都将被接受,具体来说,设您的答案为 a ,标准答案为 b ,当且仅当 max(1,∣b∣)∣a−b∣≤10−6 时,您的答案都将被接受。
样例1
输入
3 1
1 2 1
3
-3 3
0 0
-3 -2
3
1 3
3 0
1 -3
4
-2 1
4 3
5 -2
-3 -5
输出
54.507981260725
说明
在这一样例中,以点 C 作为起点 S0 。依次打印图形一、三、二,具体路径描述如下:
首先打印图形一 (C→A→B→C) ,耗时 132+5+13≈12.84819196 。
随后打印图形三 (C→G→B→I→J→G),耗时 140+26+73+37≈26.05034111。
最后打印图形二 (G→D→E→F→D→A),耗时 26+13+13≈6.60555128 。
别忘了加上图形与图形间的移动时间,这一部分耗时 15+13+10≈9.00359691 。