0

Помогите решить задачку, мой код не проходит тесты из-за времени работы. Дан массив неотрицательных чисел, необходимой найти максимальный отрезок массива, с суммой меньше заданной. Я ищу эту суммы обычным 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;
}

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

10 7
1
4
0
5
6
0
0
1
5
3
0 100
0 5
4 11
4 12
4 13
10 100

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

10
3
8
9
9
10
8

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

2
  • бинарный поиск - вполне хорошая идея. А что именно вам непонятно? У вас есть S[i] = sum(a[j], j < i). Вам нужно найти позицию в которой S[i] < S[l] + sum. Собственно бинарный поиск в чистом виде.
    – pavel
    2 мар 2022 в 10:32
  • Я всё равно, честно, не понимаю, как массив с суммами нулевого элемента до i, может помочь мне найти с помощью бинарного поиска сумму от l до r. Можете, пожалуйста, написать код, как это реализовать 2 мар 2022 в 10:44

1 ответ 1

0
#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;
}

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

2
  • Тут что-то не так и получается бесконечный цикл. Как я понимаю, условие arr[k]>sum просто не выполняется никогда 2 мар 2022 в 14:04
  • @HandcraftingCountry вот примерный вариант. ideone.com/yfgq1a писал на с++, но функция ровно такая же вроде бы) P.S. почему в тексте вопроса вы написали 8 в последнем ответе я не знаю.
    – pavel
    2 мар 2022 в 17:53

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.