1题 数组分割成左右两部分，两端和的乘积尽量大，转化为两端和的差值尽量小。因为和为定值，两个数相差越小积越大。高中时学的不等式。不用用double
题意：有个数组arr[0..n-1]，从某个位置x将数组分成左右两部分，返回左侧数组和 乘以 右侧数组和 的 积值最大时的切割位置x。例如[1,2,3]，可分割为[1,2] [3] 和 [1] [2,3]两种情况。积值分别为9、5
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; ++i) {
arr[i] = sc.nextInt();
}
long[] preSum = new long[n + 1];
for (int i = 0; i < n; ++i) {
preSum[i + 1] = preSum[i] + arr[i];
} // sum[i..j] = preSum[j+1] - preSum[i]
long delta = Long.MAX_VALUE;
int target = 0;
for (int i = 1; i < n; ++i) {
long right = preSum[n] - preSum[i];
long left = preSum[i];
long tmp = Math.abs(right - left);
if (tmp < delta) {
delta = tmp;
target = i;
}
}
System.out.println(target);
}
}
2题 不会。暴力打表找规律 [1..n/2 + 1]左边结果为0
当r <= n/2+1时，结果全为0。这样提交只能过3%
当
当
题意：前n个自然数1,2,..,n，连续的x个元素一组，剩余的不够x的元素计数加加。x从1取到n，可以得到[1..n]的总剩余计数次数。返回[l,r]的每个元素的总剩余次数。
例如n = 4, x = 1时无剩余数，x=2时无余数，x=3时剩余一个4，x=4时无剩余数。所以[1,4]总剩余次数[0,0,0,1]
全部评论
(8) 回帖