Самый длинный отрезок с суммой меньше заданной

Question

Помогите решить задачку, мой код не проходит тесты из-за времени работы. Дан массив неотрицательных чисел, необходимой найти максимальный отрезок массива, с суммой меньше заданной. Я ищу эту суммы обычным while, но решение получается слишком медленное, не знаю, как его ускорить.
Вот мой код

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n);


int main() {;
    FILE *f = fopen("input.txt","r");
    FILE *s = fopen("output.txt","w");
    uint32_t n,t,l;
    uint64_t sum;
    fscanf(f,"%d",&n);
    fscanf(f,"%d",&t);
    uint32_t *arr = malloc(sizeof (uint32_t) * n);
    for( int i = 0; i < n; i++){
        fscanf(f,"%d",&arr[i]);
    }
    for( int i = 0; i < t; i++){
        fscanf(f,"%d %lld",&l,&sum);
        Query(l,sum,arr,n);
    }
    return 0;
}

uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n){
    uint64_t summy = 0;
    uint32_t  i;
    for( i = l ; i < n; i++){
        summy+= arr[i];
        if (summy > sum){
            return i;
        }
    }
    return i;
}

Пример теста Входные данные

Выходные данные

Первые 2 цифры - это кол-во элементов массива и кол-во вопросов к нему.
Дальше идут n элементов массива.
Потом идут пары цифр l и sum - необходимо найти максимальный отрезок массива с началом в l и суммой меньше, чем sum.
Индексация идёт, как в обычном C. Начинается массив с 0 и идёт до n.
Друзья советуют искать сумму от 0 до i, а потом как-то бинарным поиском находить нужный отрезок, но я совсем не понимаю как такое реализовать(

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n);


int main() {;
    FILE *f = fopen("input.txt","r");
    FILE *s = fopen("output.txt","w");
    uint32_t n,t,l,temp;
    uint64_t sum;
    fscanf(f,"%d",&n);
    fscanf(f,"%d",&t);
    uint64_t *arr = malloc(sizeof (uint64_t ) * n);
    arr[0] = 0;
    for( int i = 0; i < n; i++){
        fscanf(f,"%d",temp);
        arr[i+1] = arr[i] + temp; 
    }
    for( int i = 0; i < t; i++){
        fscanf(f,"%d %lld",&l,&sum);
        Query(l,sum,arr,n);
    }
    return 0;
}

uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n){
    // [l, n]
    n++;
    // [l, n)
    sum += arr[l];
    while (l + 1 < n) {
        uint32_t k = (l + n) / 2;
        if (arr[k] > sum) l = k; else n = k;
    }
    return l;
}

Примерно так. Общая идея - иметь массив префиксных сумм, и на каждый запрос делать бинарный поиск. (спасает что отрицательных чисел нет).

БЛОГ НА HUSL

Самый длинный отрезок с суммой меньше заданной

Ответы (1 шт):