1125.修建高楼 题解

题解

我终于有资格写题解了！！！（bushi

2021刘裕康3友情提供
——————————————————————————————————————————————————————题目描述
C 市有一条东西走向的“市河”。C 市的市长打算在“市河”的其中一条岸边自东往西 的 n 个位置（可以将这 n 个位置看成在一条直线上，且位置不会重叠）依次建造高楼。
C 市的设计部门设计了 T 个方案供市长挑选（方案编号为 1 到 T）。每个方案都提供了 建造的每幢高楼的高度，自东向西依次为 h1，h2，h3，...，hn-1，hn。每幢楼房的高度在 1 到 n 之间（包括 1 和 n），且各不相同。
市长在挑选设计方案时，喜欢 n 幢高楼中任意 3 幢（包括不连续的 3 幢）有一定的“梯 度美”。所谓“梯度美”是指这 3 幢高楼满足：第 j 幢的高度 hj-第 i 幢的高度 hi=第 k 幢的 高度 hk-第 j 幢的高度 hj (1≤ i < j < k ≤ n)。
市长喜欢方案中这种“梯度美”现象越多越好。请编程帮市长挑选一下设计方案吧。

——————————————————————————————————————————————————————————————————————————————————
输入&输出
**
输入从文件中读取，输入共 T+1 行。
第一行两个整数 T 和 n，分别表示设计部门提供的方案总数和打算建造的高楼数。
接下来每一行表示一种方案。第 i+1 行表示第 i 种方案，每行 n 个整数，依次表示每幢 高楼打算建造的高度。

——————————————————————————————————————————————————————————————————————————————————

输出包含两个整数，第一整数为出现“梯度美”次数最多的方案，第二个整数为对应方案“梯 度美”出现的次数。如果出现“梯度美”次数最多的方案有多个，输出方案编号较小的方案。

**

样例输入
NO.1
2 5
3 1 2 4 5
3 1 2 5 4
No.2
2 6
3 5 4 6 1 2
1 6 5 4 2 3

样例输出
NO.1
1 1
NO.2
2 4

数据范围限制

50%的测试点输入数据保证 1≤T≤30，且 3≤n≤500
100%的测试点输入数据保证 1≤T≤50，且 3≤n≤2000

提示
【样例 1 解释】
输入中共有 2 个方案，打算建造 5 幢高楼。
第一个方案每幢高楼高度依次为 3，1，2，4，5，其中第 1 幢，第 4 幢和第 5 幢高度出 现“梯度美”（3，4，5），这 3 幢高楼的后一幢比前一幢依次高 1。
第二个方案每幢高楼高度依次为 3，1，2，5，4，没有出现“梯度美”。
【样例 2 解释】
输入中共有 2 个方案，打算建造 6 幢高楼。
第一个方案每幢高楼高度依次为 3，5，4，6，1，2，没有出现“梯度美”。
第二个方案每幢高楼高度依次为 1，6，5，4，2，3，出现了 4 次“梯度美”，分别是（1， 2，3）、(6，5，4)、（6，4，2）、（5，4，3）。

思路：

首先进行标记，设a[i]为存储方案的数组，设ans[i]为存储每一个方案符合b-a=c-b的任意三个数的数量，
输入之后，设f[i]为存储方案顺序中位置的数组，有f[a[i]]=i，表示为方案中的第i个，
然后通过观察得到，符合条件的三个数，假设为a,b,c，a与b,b与c之间的最大间隔为(n-1)/2，
接下来可以通过两个for循环进行搜索，
外层为i=1;i<=n-2;i++(因为是三个数，所以a最多只能在n-2这个位置)
，里层为j=1;j<=(n-1)/2;j++,
判断语句为if(i+j+j<=n），就符合第一个条件，a b c都在n的范围内，
然后i代表a的下标，i+j代表b的下标，i+j*2代表 c的下标，即a=a[i],b=a[i+j],c=a[i+j*2],接着，只要a b c满足不上升或不下降，就ans[i]++
最后通过比较 ans[1]到ans[t]，即可得出最优解。

想要代码？

提示：文章中有代码超链接，即点击某一个字符有可能发现代码