HDU3440 House Man
2021/6/5 10:20:55
本文主要是介绍HDU3440 House Man,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3044 Accepted Submission(s): 1275
The man can travel for at most a certain horizontal distance D in a single jump. To make this as much fun as possible, the crazy man want to maximize the distance between the positions of the shortest house and the tallest house.
The crazy super man have an ability—move houses. So he is going to move the houses subject to the following constraints:
1. All houses are to be moved along a one-dimensional path.
2. Houses must be moved at integer locations along the path, with no two houses at the same location.
3. Houses must be arranged so their moved ordering from left to right is the same as their ordering in the input. They must NOT be sorted by height, or reordered in any way. They must be kept in their stated order.
4. The super man can only jump so far, so every house must be moved close enough to the next taller house. Specifically, they must be no further than D apart on the ground (the difference in their heights doesn't matter).
Given N houses, in a specified order, each with a distinct integer height, help the super man figure out the maximum possible distance they can put between the shortest house and the tallest house, and be able to use the houses for training.
Input In the first line there is an integer T, indicates the number of test cases.(T<=500)
Each test case begins with a line containing two integers N (1 ≤ N ≤ 1000) and D (1 ≤ D ≤1000000). The next line contains N integer, giving the heights of the N houses, in the order that they should be moved. Within a test case, all heights will be unique.
Output For each test case , output “Case %d: “first where d is the case number counted from one, then output a single integer representing the maximum distance between the shortest and tallest house, subject to the constraints above, or -1 if it is impossible to lay out the houses. Do not print any blank lines between answers.
Sample Input 3 4 4 20 30 10 40 5 6 20 34 54 10 15 4 2 10 20 16 13
Sample Output Case 1: 3 Case 2: 3 Case 3: -1
Author jyd
Source 2010 ACM-ICPC Multi-University Training Contest(1)——Host by FZU
Recommend We have carefully selected several similar problems for you: 3439 3433 3442 3438 3437
题意:有n栋房子,给出每栋房子的高度和开始时的相对位置,可以移动一些房子,但不能改变这些房子的相对位置,现在从最矮的房子开始,每次跳至比它高的第一栋房子, 而且每次跳跃的水平距离最大是D,房子不能在同一位置,只能在整点位置。问最矮的房子和最高的房子之间的最大距离可以是多少?如果不能从最矮的房子到达最高的房子则输出-1.
分析:令d[i]表示第i栋房子与第一栋房子之间的最大距离,那么我们要求的就是的的d[n],求最短路即可,首先每栋房子之间的相对位置已经确定且不能在同一位置,那么d[i+1] > d[i],每次要跳至比它高的房子上,那么我们需要对房子按高度排序。因为开始时已经规定标号小的点在标号大的点的左边,这样,我们如果从标号大的点到标号小的点,建一条这样的边就会有问题,只能按小到大建边,而且如果两个排序后相邻房子之间的标号大于D的话则不可能到最高的房子,因为房子不可能在同一位置,他们之间的距离至少是D。约束条件只有这两者,建边时需要处理一下方向。最后如果最高的房子标号比矮的房子小的话,则以最高的房子为源点进行spfa,如果存在负环则输出-1.
杭电炸了。。。放个std
#include <bits/stdc++.h> using namespace std; const int N = 1010, M = 10000; const int INF = 0x3f3f3f3f; struct house{ int he, id; bool operator < (const house& x)const { return he < x.he; } }h[N]; struct edge{ int v, d, next; edge(int v, int d, int n):v(v), d(d), next(n){} edge(){} }ed[M]; int head[N], d[N], vis[N], cnt[N]; int n, s, e, k; queue<int> q; void init() { k = 0; memset(head, -1, sizeof(int) * n); memset(d, INF, sizeof(int) * n); memset(vis, 0, sizeof(int) * n); memset(cnt, 0, sizeof(int) * n); for (int i = 0; i < n; i++) h[i].id = i; while (!q.empty()) q.pop(); } void add(int u, int v, int d) { ed[k] = edge(v, d, head[u]); head[u] = k++; } int spfa() { d[s] = 0; cnt[s]++; q.push(s); while (!q.empty()) { int x = q.front(); q.pop(); vis[x] = 0; for (int i = head[x]; i != -1; i = ed[i].next) { int t = ed[i].v; if (d[t] > d[x] + ed[i].d) { d[t] = d[x] + ed[i].d; if (!vis[t]) { vis[t] = 1; q.push(t); if (++cnt[t] > n) return -1; } } } } return d[e]; } int main() { int t, ca = 0; scanf("%d", &t); while (t--) { int d; scanf("%d %d", &n, &d); init(); for (int i = 0; i < n; i++) scanf("%d", &h[i].he); sort(h, h+n); int flag = 1; for (int i = 0; i < n-1 && flag; i++) { add(i+1, i, -1); int u = min(h[i].id, h[i+1].id), v = max(h[i].id, h[i+1].id); if (v - u > d) flag = 0; add(u, v, d); } s = min(h[0].id, h[n-1].id), e = max(h[0].id, h[n-1].id); printf("Case %d: %d\n", ++ca, flag ? spfa() : -1); } return 0; }
这篇关于HDU3440 House Man的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)