0

Всем привет, решал задачу, и написал работающее решение. Одна проблема - по всем тестам не проходит по времени. Суть в том что вводимый номер билетика может достигать длинны 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;
}
2

2 ответа 2

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

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

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

введите сюда описание изображения

13
  • Какая логика в этом коде? Попросту говоря как он работает? 12 ноя 2018 в 18:53
  • да тут все просто как три копейки, сначала плюсуем все значения, кроме последнего(это будет условное деление на левую и правую части номера билетика), а дальше начинаем по очереди прибавлять одну цифру к правой части, и отнимать одну из левой части. если части совпали то билетик счастливый (левая часть в коде это а1, правая-а2)
    – Slav9n92
    12 ноя 2018 в 18:57
  • Пока переписывал уже всё сам понял =) Спасибо, действительно простое решение. 12 ноя 2018 в 19:02
  • да пожалуйста, хоть мозги размял малька)
    – Slav9n92
    12 ноя 2018 в 19:03
  • =) Всегда полезно 12 ноя 2018 в 19:03
0

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

Код на 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;
}
1

Ваш ответ

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

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