题目描述
blablabla
样例
import java.io.*;
public class Main{
static int N=100010;
static int[] a=new int[N];
static int neg,pos;//分别存储差分中负数的绝对值和整数的绝对值;
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
String[] b=br.readLine().split(" ");
String[] c=br.readLine().split(" ");
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(b[i-1])-Integer.parseInt(c[i-1]);//差分数组从1开始
}
for(int i=n;i>0;i--){//从后面开始差分
a[i]-=a[i-1];
if(a[i]>0){
pos+=a[i];
}
else{
neg-=a[i];
}
}
System.out.print(Math.max(neg,pos));
}
}
//对区间的调整转换为对数的调整,可以对一个数加一或减一,或者对一个数加一,另一个减一;
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla