14165: 【原4165】数列操作

题目描述

author: 侯不会 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4165

Sample Input

``````3
3 4 5
6 7 8
``````

Sample output

``````3
``````

q4x3's solution

``````/**
* 数学题
* 求出差异数组
* 无脑扫描: 分正负串
* 一串正数中，如果当前扫到的数大于左侧相邻的数，则加上差，否则继续
* 负数类似
* 差分: [lo, hi)同时+1相当于其差分数组(右减左)lo加1，hi减1
**/
#include <iostream>

using namespace std;

int N;
long long a[100233], b[100233], c[100233], tmp1, tmp2;

int main() {
cin >> N;
for(int i = 0;i < N;++ i)
cin >> a[i];
for(int i = 0;i < N;++ i)
cin >> b[i];
for(int i = 1;i <= N;++ i)
c[i] = b[i - 1] - a[i - 1];
/**
* 差分法
for(int i = 1;i <= N;++ i) {
if(c[i] >= c[i - 1]) tmp1 += (c[i] - c[i - 1]);
else tmp2 += (c[i - 1] - c[i]);
}
if(tmp1 >= tmp2) cout << tmp1 << endl;
else cout << tmp2 << endl;
* */

/**
* 无脑扫描法
* */
for(int i = 1;i <= N;++ i) {
if(c[i] == 0) continue;
if(c[i] > 0) {
if(c[i - 1] >= 0) {
if(c[i - 1] < c[i]) ans += (c[i] - c[i - 1]);
continue;
} else {
ans += c[i];
continue;
}
} else if (c[i] < 0) {
if(c[i - 1] >= 0) {
ans -= c[i];
continue;
} else {
if(c[i - 1] > c[i]) ans += (c[i - 1] - c[i]);
continue;
}
}
}
cout << ans << endl;
}
``````

victrid's solution

``````#include <iostream>
using namespace std;
inline int sgn(int& a) {
if (a == 0)
return 0;
if (a > 0)
return 1;
if (a < 0)
return -1;
return 0;
}
int main() {
int n;
cin >> n;
int* list = new int[n];
for (int i = 0; i < n; i++) {
cin >> list[i];
}
int proc;
for (int i = 0; i < n; i++) {
cin >> proc;
list[i] -= proc;
}
int sign            = 0;
int height          = 0;
long long totalstep = 0; //???
for (int i = 0; i < n; i++) {
if (sign != sgn(list[i])) {
height = sgn(list[i]) * list[i];
sign   = sgn(list[i]);
totalstep += height;
continue;
}
if (sgn(list[i]) * list[i] > height) {
totalstep += (sgn(list[i]) * list[i] - height);
height = sgn(list[i]) * list[i];
continue;
}
if (sgn(list[i]) * list[i] <= height) {
height = sgn(list[i]) * list[i];
continue;
}
}
cout << totalstep;
return 0;
}
``````

zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4165.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, a[100005];
void init(){
for (int i = 1; i <= n; ++i)
int mini = 0;
for (int i = 1; i <= n; ++i)
}
inline int sgn(int x){
return (x == 0 ? 0: (x > 0 ? 1: -1));
}
void solve(){
ll ans = 0;
for (int i = 1; i <= n; ){
int j = i;
while (j <= n && sgn(a[i]) == sgn(a[j]))
++j;
if (sgn(a[i]) > 0){
int lst = 0;
for (int t = i; t < j; ++t){
if (a[t] > lst) ans += a[t] - lst;
lst = a[t];
}
}else if (sgn(a[i]) < 0){
int lst = 0;
for (int t = i; t < j; ++t){
if (-a[t] > lst) ans += -a[t] - lst;
lst = -a[t];
}
}
i = j;
}
printf("%lld\n", ans);
}
int main(){
init();
solve();
return 0;
}
``````