Счастливый билетик Задача C++

142

14 апреля 2019, 06:50

Всем привет, решал задачу, и написал работающее решение. Одна проблема - по всем тестам не проходит по времени. Суть в том что вводимый номер билетика может достигать длинны 1000000 символов, полное условие задачи и мое решение ниже, как переделать это решение чтобы тратилось меньше времени?(Раньше с векторами не работал, а по другому нельзя ибо нельзя сделать массив длинною [1000000])

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
    ifstream inp;
    ofstream otp;
    inp.open("input.txt");
    otp.open("output.txt");
    double k = 0, n = 0, s1 = 0, s2 = 0;
    vector<int> a(1000000);
    inp >> n;
    for (int i = 0; i < n; i++) {
        inp >> a[i];
    }
    for (; k <= n; k++) {
        s1 = 0;
        s2 = 0;
        if (k == n) {
            otp << "-1";
            break;
        }
        else {
            for (int i = 0; i < k; i++) {
                s1 += (int)a[i];
            }
            for (int i = k; i < n; i++) {
                s2 += (int)a[i];
            }
            if (s1 == s2) {
                otp << k;
                break;
            }
        }
    }

    return 1;
}

Answer 1

нашел эту задачу на сайте e-olymp, в общем решил вот так

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[]){
    int n;
    cin>>n;
    unsigned int a1=0,a2=0;
    vector<unsigned int> vec;
    while(n--){
        unsigned int temp;
        cin>>temp;
        a1+=temp;
        vec.push_back(temp);
    }
    unsigned long step=vec.size()-1;
    long long min=-1;
    while(step){
        a1-=vec[step];
        a2+=vec[step];
        if(a2==a1){
            min=step;
        }
        step--;
    }
    if(min==-1)
        cout<<"-1"<<endl;
    else
        cout<<min<<endl;
    return 0;
}

вам надо будет только считывание из файла сделать

поучилось даже малька ускорить

Answer 2

Вот, если интересно, решение с частичными суммами:

Код на ideone

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
    // ifstream inp;
    // ofstream otp;
    // inp.open("input.txt");
    // otp.open("output.txt");
    auto &inp = cin;
    auto &otp = cout;

    double k = 0, n = 0, s1 = 0, s2 = 0;
    vector<int> a(1000000);
    inp >> n;
    for (int i = 0; i < n; i++) {
        inp >> a[i];
    }
    // Считаем частичные суммы
    vector<int> s(1000000);
    s[0] = a[0];
    for (int i = 1; i < n; i++) {
        s[i] = s[i-1] + a[i];
    }
    for (; k <= n; k++) {
        s1 = 0;
        s2 = 0;
        if (k == n) {
            otp << "-1";
            break;
        }
        else {
            // for (int i = 0; i < k; i++) {
            //  s1 += (int)a[i];
            // }
            // for (int i = k; i < n; i++) {
            //  s2 += (int)a[i];
            // }
            // Используем частичные суммы вместо прямого подсчета сумм
            s1 = s[k];
            s2 = s[n-1] - s[k];
            if (s1 == s2) {
                otp << k + 1;
                break;
            }
        }
    }
    return 0;
}