P9787 [ROIR 2020 Day2] 最大乘积 题解

KDL_ANIPLEX · 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;
     }