题解
开始准备用贪心来做,后来发现山峰的高度变换后,可能导致一系列问题,比如最高峰和最低峰变成了其他山峰,因为有后效性,所以无法直接使用贪心。
但是数据量非常小,我们可以对100内每一对l
和r
进行枚举(其中l
和r
差值恒为17),在这对值的控制下,我们对每座山峰进行“修剪”,保证其高度在[l,r]
区间内,即差值恒为17
(此时花费最小),然后找出使得花费最小的一对l、r
对应的花费即可。
#include <bits/stdc++.h>
using namespace std;
inline int mypow(int n) { return n * n; }
int arr[1005];
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> arr[i];
int tot = 1 << 30;
// 在1到100中,枚举每一对差值刚好为17的数(i, i + 17) 1 <= i <= 83
for(int i = 1; i < 84; i++) {
int tmp = 0, l = i, r = i + 17;
for(int j = 0; j < n; j++) { // 枚举处理每座山峰的情况,让每座山峰都满足差值小于等于17的情况
if(arr[j] < l) tmp += mypow(arr[j] - l);
else if(arr[j] > r) tmp += mypow(arr[j] - r);
}
tot = min(tot, tmp); // 找差值最小的情况
}
cout << tot << endl;
return 0;
}
i是从0到83,因为山峰高度最低为0
%%%%%
是从0到100枚举,所以i是从0到83
需要修改
数据过不去,需要将高度全部自增1
只需要将i从0开始即可
用贪心做会导致二次修改吧
我一开始也是贪心
山峰高度不能是0吗
可以为0,题目是说
0 ~100
之间%