99802024-03-22 17:37:28abelke2Leggyorsabb pénzkeresés (50)cpp17Elfogadva 50/5035ms15860 KiB
#include <iostream>
#include <vector>

void kiirVektor(std::vector<int> vek) {
    for (int i : vek) {
        std::cout << i << " ";
    }
    std::cout << "\n------------------\n";
}

void beolvas(int& n, int& penztOsszeszedni, std::vector<int>& napok) {
    std::cin >> n >> penztOsszeszedni;
    napok.resize(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> napok[i];
    }
}

int megold(int n, int penztOsszeszedni, std::vector<int> napok) {
    std::vector<int>addigMennyit = std::vector<int>(n);
    addigMennyit[0] = napok[0];
    for (int i = 1; i < n; ++i) {
        addigMennyit[i] = addigMennyit[i - 1] + napok[i];
    }
    //kiirVektor(addigMennyit);

    //Ket indexet hasznalva az intervallumokat linearis idoben ellenorizzuk
    int szam = 0;
    int i = 0;
    int j = 0;
    //Elnavigalunk a sorrendben elso (nem feltetlen optimalis) megoldashoz
    while (j < n && addigMennyit[j] < penztOsszeszedni) {
        ++j;
    }
    szam = j - i + 1;

    while (j < n && i < n - 1) {
        //Lepunk egyet a bal oldali indexszel jobbra. Ha ezzel jobb megoldast talalunk, azt megjegyezzuk, ellenkezo
        //esetben jobb indexszel lepunk jobbra
        int elotte = -1;
        if (i >= 1) {
            elotte = addigMennyit[i - 1];
        }
        else {
            elotte = 0;
        }
        if (i + 1 <= j && addigMennyit[j] - addigMennyit[i] >= penztOsszeszedni) {
            ++i;
            if (j - i + 1 < szam) {
                szam = j - i + 1;
            }
        }
        else if(j < n) {
            ++j;
        }
        else {
            ++i;
        }
    }
    return szam;
}

int main() {
    int n = 0;
    int penztOsszeszedni = 0;
    std::vector<int>napok;
    beolvas(n, penztOsszeszedni, napok);

    int megoldas = megold(n, penztOsszeszedni, napok);
    std::cout << megoldas;

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1808 KiB
2Elfogadva0/035ms4788 KiB
3Elfogadva2/23ms2844 KiB
4Elfogadva2/23ms2788 KiB
5Elfogadva2/23ms3028 KiB
6Elfogadva2/26ms3484 KiB
7Elfogadva2/26ms3580 KiB
8Elfogadva2/26ms3756 KiB
9Elfogadva2/26ms3892 KiB
10Elfogadva2/26ms4064 KiB
11Elfogadva2/235ms6736 KiB
12Elfogadva2/235ms7452 KiB
13Elfogadva2/235ms8176 KiB
14Elfogadva2/235ms8752 KiB
15Elfogadva2/235ms9288 KiB
16Elfogadva2/235ms10008 KiB
17Elfogadva2/235ms10460 KiB
18Elfogadva2/235ms10940 KiB
19Elfogadva2/235ms11552 KiB
20Elfogadva2/235ms12116 KiB
21Elfogadva2/235ms12744 KiB
22Elfogadva2/235ms13208 KiB
23Elfogadva2/235ms13624 KiB
24Elfogadva2/235ms14104 KiB
25Elfogadva2/235ms14712 KiB
26Elfogadva2/235ms15280 KiB
27Elfogadva2/235ms15860 KiB