shunfurh
编程介的小学生
2018-12-16 07:20
采纳率: 92.7%
浏览 1.9k

定序列A={A1,A2,...,An}, 要求改变序列A中的某些元素,形成一个严格单调的序列B

Problem Description
给定序列A={A1,A2,...,An}, 要求改变序列A中的某些元素,形成一个严格单调的序列B(严格单调的定义为:Bi<Bi+1,1≤i<N)。

我们定义从序列A到序列B变换的代价为cost(A,B)=max(|Ai−Bi|)(1≤i≤N)。

请求出满足条件的最小代价。

注意,每个元素在变换前后都是整数。

Input
第一行为测试的组数T(1≤T≤10).

对于每一组:
第一行为序列A的长度N(1≤N≤105),第二行包含N个数,A1,A2,...,An.
序列A中的每个元素的值是正整数且不超过106。

Output
对于每一个测试样例,输出两行:

第一行输出:"Case #i:"。i代表第 i 组测试数据。

第二行输出一个正整数,代表满足条件的最小代价。

Sample Input
2
2
1 10
3
2 5 4

Sample Output
Case #1:
0
Case #2:
1

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐