萌新写文章,请大家多多指教。
正解1:暴力模拟。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a[1010];
int ans = 0;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i < n; i ++)
{
ans = max(ans, abs(a[i + 1] - a[i]));
}
cout << ans;
}
正解2:差分数组
求的答案好像是差分数组的绝对值的最大值。
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n;
int a[N];
int b[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i < n; i ++) b[i] = abs(a[i + 1] - a[i]);
int maxn = INT_MIN;
for(int i = 1; i < n; i ++) maxn = max(maxn, b[i]);
cout << maxn;
return 0;
}
下面的解法就是恶搞,没这个必要,大家看着玩就行了。
奇怪解法1:dp
硬搞肯定能过。
f[i]表示前i个数的最大波动。
状态转移很简单,就是直接看看要还是不要。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n;
int a[N];
int f[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i < n; i ++) f[i] = max(f[i - 1], abs(a[i + 1] - a[i]));
cout << f[n - 1];
}
奇怪解法2:线段树(
线段树维护区间最大波动。
然后发现根本没有修改操作。
所以说还是可以用线段树做的。
当然,也可以用splay来搞。。。
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n;
int w[N];
int b[N];
struct Node
{
int l, r;
int maxn;
}tr[N * 4];
void pushup(int u)
{
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, abs(b[r])};
return ;
}
else
{
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
int ans = 0;
if(r <= mid) ans = max(ans, query(u << 1, l, r));
if(l > mid) ans = max(ans, query(u << 1 | 1, l, r));
int left = query(u << 1, l, r);
int right = query(u << 1 | 1, l, r);
return max(ans, max(left, right));
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n ;i ++) cin >> w[i];
for(int i = 1; i < n; i ++) b[i] = w[i + 1] - w[i];
build(1, 1, n);
cout << query(1, 1, n);
}
哈哈哈哈哈恶搞结束。。。
Orz
水题解的屑cht