Skip to content

14165: 【原4165】数列操作

题目

题目描述

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

Description

侯不会又遇到了一个不会的问题,现在他来请教你:
给定一个长度为\(N\)的整数数列\(A\),并且可以对这个数列进行一种操作:将某个区间里的数全部\(+1\)或\(-1\)
再给一个长度相同的整数数列\(B\),请问最少需要几次可以将\(A\)变成\(B\)?

Input Format

输入共三行。
第一行一个整数\(N\)
第二行是数列\(A\)
第三行是数列\(B\)

Output Format

输出共一行,包含一个正整数,表示最少需要的次数。

Sample Input

3  
3 4 5  
6 7 8

Sample output

3

数据范围

对于100%的数据,\(N <= 10^5\),\(|A_i|, |B_i| <= 10^6\)

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 read(){
    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(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    int mini = 0;
    for (int i = 1; i <= n; ++i)
        a[i] = read() - a[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;
}