我們把所給數字制成條形統計圖，如果確定了最終平面位置，我們把最終平面想象成地面，所有的條形圖的上邊緣想象成從地面向上或向下長出的山峰。我們的結果就是所有右側山坡的垂直高度之和加上最右面一點到地面的距離。我們發現在兩端點豎直高度值之間平移地面，結果不會有變化。如果移出這個范圍，右側山坡的垂直高度之和不變，而最右邊一點到地面的距離會憑空增加。所以地面必然在兩端點豎直高度之間。我們只需要計算右側山峰高度值和即可，不妨把地面定在最左側點的高度。

View Code #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define maxn 1000006

int n, f[maxn], p[maxn];
long long sum = 0;
long long ans = 0;

long long min(long long x, long long y)
{
if (x < y)
return x;
return y;
}

void input()
{
int tot = 1, a;
scanf("%d", &n);
scanf("%d", &f[0]);
for (int i = 1; i < n; i++)
{
scanf("%d", &a);
if (a != f[tot - 1])
f[tot++] = a;
}
n = tot;
}

void work()
{
for (int i = 1; i < n; i++)
p[i] = f[i] - f[i - 1];
sum = 0, ans = 0;
for (int i = 1; i < n; i++)
{
if (sum * p[i] < 0)
ans += min(abs(sum), abs(p[i]));
sum += p[i];
}
sum = abs(sum);
ans += sum;
}

int main()
{
//freopen("D:\\t.txt", "r", stdin);
int t;
scanf("%d", &t);
for (int i = 0; i < t; i++)
{
input();
work();
printf("Case %d: %I64d %I64d\n", i + 1, ans, sum + 1);
}
return 0;
}

總結

以上是生活随笔為你收集整理的hoj3434的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。