hihocoder-1704-#1704 : 循环数组

柔光的暖阳◎ 2022-05-27 12:25 165阅读 0赞

### \#1704 : 循环数组 ###

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

### 描述 ###

给定包含N个整数的数组A1, A2, ... AN，你可以选择任意一个Ai，将Ai旋转到数组第一项，即将数组变成：

Ai, Ai+1, Ai+2, ... AN, A1, A2, ..., Ai-1

现在小Hi希望旋转之后的数组满足：

对于任意K(1 ≤ i ≤ N)，前K项的和都是正数。

例如对于A=\[3, -5, 2, -2, 3, 0\]，旋转成\[3, 0, 3, -5, 2, -2\]满足条件。

请你输出i，代表将Ai旋转到第一项满足条件。

如果有多解，你可以输出任意一个i。如果无解输出-1。

### 输入 ###

第一行包含一个整数N。

第二行包含N个整数A1, A2, ... AN。

对于50%的数据，1 ≤ N ≤ 1000

对于100%的数据，1 ≤ N ≤ 100000, -1000000 ≤ Ai ≤ 1000000

### 输出 ###

一个整数表示答案。

样例输入

6  
    3 -5 2 -2 3 0

样例输出

思路：倒序查找，先找到最大的和在什么地方，然后正序查找，如果最大的和加上调换后的数组值仍然小于0或flag=0；则不存在该点

代码：

#include<queue>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    long long a[1000100];
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            int i,j,ans=0,flag=0,sum=0,maxn=0;
            for(i=0;i<n;i++)
                scanf("%lld",&a[i]);
            for(i=n-1;i>=0;i--)
            {
                sum+=a[i];//倒序查找和在哪个位置有最大值
                if(sum>maxn)
                {
                    maxn=sum;
                    flag=i+1;
                }
            }
            int m=maxn;
            for(i=0;i<flag-1;i++)
            {
                m+=a[i];//最大的和加上调换之后的和
            }
            if(m<=0||flag==0)//如果最大的数加上调换之后的和仍然小于0或flag=0则不存在
                printf("-1\n");
            else
                printf("%d\n",flag);
        }
        return 0;
    }