Offer收割]编程练习赛50---循环数组

谁借莪１个温暖的怀抱￠ 2022-05-29 04:00 144阅读 0赞

描述
    给定包含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
    样例输出
    5

#include <cstdlib>
    #include <cstdio>
    
    using namespace std;
    int a[100001];
    int main(int argc, char *argv[])
    {
        int n,j;
        long long sum;
        while(~scanf("%d",&n)){
        sum=0;
        for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
        }
        j=0;
        for(int i=0;i<n-j;i++){
            sum=sum+a[i];
            while(sum<=0)
            {
                 j++;
                 if(i<n-j)
                 sum+=a[n-j];
                 else
                 break;
            }
        }
        if(sum>0)
        printf("%d\n",n-j+1);
        else
        printf("-1\n");
        }
        system("PAUSE");
        return EXIT_SUCCESS;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关循环和数组大厂手写算法题练习

练习一：飞机票需求: 机票价格按照淡季旺季、头等舱和经济舱收费、输入机票原价、月份和头等舱或经济舱。按照如下规则计算机票价格：旺季（5-10月）头等舱9折，经济舱

红太狼/ 2024年03月31日 02:26/ 0 赞/ 59 阅读

相关【OJ基础练习大全】大数问题+循环数组

一、整理题目大数问题 1. 大数相加 2. 大数相减 3. 再分麦粒循环数组模拟 1. 狱史问题 2. 玛雅日历 3. All in All 二、解题

Myth丶恋晨/ 2022年11月12日 14:58/ 0 赞/ 134 阅读

相关 [Offer收割]编程练习赛38 题目1 : 漏写的数字

题目1 : 漏写的数字时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB <table style="border-collapse:c

蔚落/ 2022年06月04日 03:28/ 0 赞/ 138 阅读

相关 Offer收割]编程练习赛50---座位问题

HIHO银行等待区有一排N个座位，从左到右依次编号1~N。现在有M位顾客坐在座位上，其中第i位坐在编号Ai的座位上。之后又陆续来了K位顾客，(K + M ≤ N) 他们

梦里梦外;/ 2022年05月29日 04:05/ 0 赞/ 132 阅读

相关 Offer收割]编程练习赛50---循环数组

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

谁借莪１个温暖的怀抱￠/ 2022年05月29日 04:00/ 0 赞/ 145 阅读

相关【剑指Offer】50数组中重复的数字

题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复

小灰灰/ 2022年05月15日 15:55/ 0 赞/ 192 阅读

相关 java编程-循环嵌套；数组定义

package day03; public class HomeWork1 { public static void main(String

矫情吗；*/ 2022年03月26日 11:14/ 0 赞/ 221 阅读

相关四面美团，收割offer

美团我是在拉勾网上投的简历，之前也投过一次，简历都没通过删选，后来让学姐帮我改了一下简历，重新投另一个部门，获得了面试机会。10月23日中午HR打电话过来预约了下午4点半面试，

逃离我推掉我的手/ 2022年02月14日 04:49/ 0 赞/ 269 阅读

相关 50.构建乘积数组《剑指Offer》(Java版)

题目描述 > 给定一个数组A\[0,1,...,n-1\],请构建一个数组B\[0,1,...,n-1\],其中B中的元素B\[i\]=A\[0\]\A\[1\]\...

布满荆棘的人生/ 2022年01月30日 13:53/ 0 赞/ 199 阅读

相关 hihoCoder [Offer收割]编程练习赛3 D子矩阵求和

[子矩阵求和][Link 1] [http://hihocoder.com/discuss/question/3005][http_hihocoder.com_discuss

逃离我推掉我的手/ 2021年12月23日 15:25/ 0 赞/ 176 阅读