传送门

描述

In Fuzhou, there is a crazy super man. He can’t fly, but he could jump from housetop to housetop. Today he plans to use N houses to hone his house hopping skills. He will start at the shortest house and make N-1 jumps, with each jump taking him to a taller house than the one he is jumping from. When finished, he will have been on every house exactly once, traversing them in increasing order of height, and ending up on the tallest house.

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.

输入

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.

输出

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.

样例

• Input
  3
  4 4
  20 30 10 40
  5 6
  20 34 54 10 15
  4 2
  10 20 16 13
• Output
  Case 1: 3
  Case 2: 3
  Case 3: -1

思路

• 题意：给个n个不同高度的房子，一个人从最低点跳跃，每次可以跳到第一个比它高的位置，最后跳到最高点，然后每次最多可以跳的距离为D，可以移动房子的水平位置，但是不能打乱房子的顺序，求从最低的房子到最高的房子之间的最大距离，没有满足情况则输出-1
• 若出现负环则不满足情况，题中求最大距离，所以建图求最短路
• 用vis数组存下每个点的访问次数，如果>=n,则必有负环
• 首先存下每个房子的位置信息set，然后根据高度排序；
  排序前，相邻房子之间：(i+1 - i >=1) => (i - i+1 <=-1) 建边i+1 i -1（从右指左）;
  排序后，i+1必然比i高，此时需比较两个房子原来的位置set，要从小的指向大的，即从左指到右
• spfa 链式向前星
• 在spfa遍历的时候，要注意最矮的房子a和最高的房子b的位置，如果a在左边，就从a跑到b；如果a在b的右边，就从b跑到a；如果a在b的右边还是从a跑到b，因为我们之前从右到左都建了权值-1的边，那么从a跑到b就一直走-1，显然是不正确的。
  

  Code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

  #include #include #include #include #include #include #include #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long int using namespace std; const int MAX=0x7fffffff; const int MIN=-0x7fffffff; const int INF=0x3f3f3f3f; const int Mod=1e9+7; const int maxn=1e3+7; int n,d,Begin[maxn],used[maxn],vis[maxn],dis[maxn]; struct Node{ int To,Dis,Next;}; Node Edge[10007];int top=0; struct House{ int high,book; bool operator < (const House& e){ return high sroad; sroad.push(t);used[t]=1;vis[t]++; while(!sroad.empty()){ int now=sroad.front();used[now]=0;sroad.pop(); for(int i=Begin[now];i!=-1;i=Edge[i].Next){ int ne=Edge[i].To; if(dis[ne]>dis[now]+Edge[i].Dis){ dis[ne]=dis[now]+Edge[i].Dis; if(!used[ne]){ vis[ne]++; if(vis[ne]>=n)return -1; used[ne]=1; sroad.push(ne); } } } } if(dis[hou[n].book]==INF)return -1; return max( dis[hou[n].book],dis[hou[1].book] ); } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); int T;scanf("%d",&T); for(int _=1;_<=T;_++){ INIT(Begin,-1);top=0; scanf("%d%d",&n,&d); for(int i=1;i<=n;i++){ scanf("%d",&hou[i].high); hou[i].book=i; } sort(hou+1,hou+n+1); for(int i=1;i