⭐每日一题⭐专栏
written by SJTU-XHW
本人学识有限，解析难免有错，恳请读者能够批评指正，本人将不胜感激！
LuoGu P4995. 跳蛙
题目描述
你是一只小跳蛙，你特别擅长在各种地方跳来跳去。
这一天，你和朋友小 F 一起出去玩耍的时候，遇到了一堆高矮不同的石头，其中第 $i$ 块的石头高度为 $h_i$，地面的高度是 $h_0 = 0$。你估计着，从第 $i$ 块石头跳到第 $j$ 块石头上耗费的体力值为 $(h_i - h_j) ^ 2$，从地面跳到第 $i$ 块石头耗费的体力值是 $(h_i) ^ 2$。
为了给小 F 展现你超级跳的本领，你决定跳到每个石头上各一次，并最终停在任意一块石头上，并且小跳蛙想耗费尽可能多的体力值。
你可以使用计算机程序帮你解决这个问题。
说明
输入格式
输入一行一个正整数 $n$，表示石头个数。
输入第二行 $n$ 个正整数，表示第 $i$ 块石头的高度 $h_i$。
输出格式
输出一行一个正整数，表示你可以耗费的体力值的最大值。
样例 1 输入
样例 1 输出
样例 2 输入
样例 2 输出
数据范围
对于 $1 \leq i \leq n$，有 $0 < h_i \leq 10 ^ 4$，且保证 $h_i$ 互不相同。
对于 $10\%$ 的数据，$n \leq 3$；
对于 $20\%$ 的数据，$n \leq 10$；
对于 $50\%$ 的数据，$n \leq 20$；
对于 $80\%$ 的数据，$n \leq 50$；
对于 $100\%$ 的数据，$n \leq 300$。
思路
第一次读题差点看错，要求消耗尽可能多的体力……这题又没辙了，还是贪心法：每次选择前遍历查找所有数中，和当前位置高度差最大的，且没有选择过的数；如果存在多个相同的高度差，那么类似八皇后问题，进行递归（dfs），最终找到最大值；
再一想，没必要啊，如果我一开始就将数据排序的话，每次相当于 “横跳” 数组两端的数据即可保证始终是最大值！时间复杂度平均在 $O(n\cdot log\space n)$，而且空间复杂度 $O(log\space n)$，比上面的想法要好；
注：这题的贪心法本人仍然没有证明出来，转化为数学命题：
对于任意一串正整数序列：$a_1,a_2,…,a_n$，$a_1^2+(a_2-a_1)^2+(a_3-a_2)^2+\cdots+(a_n-a_{n-1})^2$ 取最大值 $\Longrightarrow$ 对任意的 $i\gt j$，$(a_i-a_{i-1})^2\ge(a_i-a_j)^2$，当 $j=i-1$ 取等；
有无会证的同学帮帮忙？
实现
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
| #include <cstdio>
using namespace std;
int divide(int* arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (arr[right] > pivot && left < right) --right;
if (left < right) arr[left] = arr[right];
while (arr[left] <= pivot && left < right) ++left;
if (left < right) arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
void quickSort(int* arr, int left, int right) {
if (left >= right) return;
int mid = divide(arr, left, right);
quickSort(arr, left, mid - 1);
quickSort(arr, mid + 1, right);
}
int main() {
int n, left, right, ans; scanf("%d", &n);
int* height = new int[n] {0};
left = 0, right = n - 1;
for (int i = 0; i < n; ++i) scanf("%d", &(height[i]));
quickSort(height, 0, n - 1);
ans += height[right] * height[right];
while (left < right) {
ans += (height[right] - height[left]) * (height[right] - height[left]); --right;
ans += (height[right] - height[left]) * (height[right] - height[left]); ++left;
}
printf("%d", ans);
return 0;
}
|
不出意外的话，就要出意外了——只拿了50分，提交了 5 遍都有问题，整个人都不好了……直到我在社区看到这句话：
蚌埠住了😶 气得我把所有数据全换成 long long
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
| #include <iostream>
using namespace std;
long long divide(long long* arr, long long left, long long right) {
long long pivot = arr[left];
while (left < right) {
while (arr[right] > pivot && left < right) --right;
if (left < right) arr[left] = arr[right];
while (arr[left] <= pivot && left < right) ++left;
if (left < right) arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
void quickSort(long long* arr, long long left, long long right) {
if (left >= right) return;
long long mid = divide(arr, left, right);
quickSort(arr, left, mid - 1);
quickSort(arr, mid + 1, right);
}
int main() {
long long n, left, right; cin >> n;
long long ans;
long long* height = new long long[n] {0};
left = 0, right = n - 1;
for (int i = 0; i < n; ++i) cin >> height[i];
quickSort(height, 0, n - 1);
ans += height[right] * height[right];
while (left < right) {
ans += (height[right] - height[left]) * (height[right] - height[left]);
--right;
ans += (height[right] - height[left]) * (height[right] - height[left]);
++left;
}
cout << ans;
delete[] height;
return 0;
}
|
