自动搬运

查看原文

来自洛谷，原作者为

	KDL_ANIPLEX 我乃是——龙！||对不起，csp_s结束再关回来

搬运于2025-08-24 22:51:50，当前版本为作者最后更新于2023-10-28 14:17:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

题意简述

给定一个自然数组成的数组 $[a_1,a_2,\ldots,a_n]$。
求出一个整数 $i(1\le i\le n)$，使得 $\sum_{j=1}^{i}{a_j}$ 与 $\sum_{j=i+1}^{n}{a_j}$ 的积最大。
对于 $100\%$ 的数据，$2 \le n \le 2\cdot 10^5, 1 \le a_i \le 10^9$。

题目分析

1. 由于 $n\le 2\cdot 10^5$，考虑 $O(n)$ 的算法。
2. 基本思路：

• 读入，读入的同时进行前缀和（记录 $\sum_{j=1}^{i}{a_j}$）。
• 重头扫一遍，根据“和不变，差小积大”的原理，记录两个因数差的绝对值最小时的 $i$。
• 输出 $i$。

3. 复杂度：

• 读入、前缀和：$O(n)$。
• 重头扫一遍：$O(n)$。
• 输出：$O(1)$。
  整体复杂度为 $O(n)$。

4. 注意事项：

• 开 longlong。

代码

#include<cstdio>
long long a[200001],s=1e17,n,l;
long long abss(long long x,long long y)//绝对值函数
{
    if (x>y) return x-y;
    return y-x;
}
int main(){
    scanf ("%d",&n);
    for (int i=1;i<=n;i++){
        int u;
        scanf ("%d",&u);//读入。
        a[i]=a[i-1]+u;//前缀和。
    }
    for (int i=1;i<=n;i++){
        long long o=abss(a[i],a[n]-a[i]);//两个因数差的绝对值。
        if (o<s) s=o,l=i;//记录目前最小的差与答案。
        else break;//小优化：如果已经比 s 大，那后面的也会比 s 大，所以退出。
    }
    printf ("%d\n",l);
    return 0;
}