VPF::помогите, пожалуйста найти ошибку

Тавасилек

Дата 28.5.2016, 17:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 28.5.2016

Репутация: нет
Всего: нет

Здравствуйте, помогите, пожалуйста. Есть задача:
Есть N станков и 2 работы. Каждая работа состоит из Si этапов. Этап характеризуется парой (n, t) чисел, где n — номер станка, а t — продолжительность этапа. Для каждой работы порядок этапов строго задан. Любой этап можно приостановить в любой момент и позже продолжить с того же момента. В каждый момент времени любая работа может выполняться только на одном станке и любой станок может выполнять только одну работу. Необходимо составить такое расписание, чтобы все работы были выполнены за минимальное время.

Формат входного файла

В первой строке содержится единственное число N. В следующих двух строках на первом месте записано число Si, а за ним — Si пар (n, t) через пробел.

И мое решение:

Код


#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Para {
    int x;
    int y;

    Para(int t=0,int s=0):x(t),y(s) {}
};

int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2);

int main()
{
    ifstream fin("input.txt");
    int n,a1,a2,b,c,i,j;
    fin >> n;
    vector<Para> v1,v2;

    ofstream fout("output.txt");
    int ans = 0;

    Para r1,r2;
    fin >> a1;
    for(j=0;j<a1;j++) {
        fin >> b;
        fin >> c;
        Para q(b,c);
        v1.push_back(q);
    }
    fin >> a2;
    for(j=0;j<a2;j++) {
        fin >> b;
        fin >> c;
        Para q(b,c);
        v2.push_back(q);
    }
    i=0;
    j=0;
    ans = vremia(i,j,ans,v1,v2);
    fout << ans;
    fout.close();
    fin.close();
    return 0;
}

int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2) {
    int b,c;
    Para r1,r2;
    if(i<v1.size()) {
        r1 = v1[i];
        b = 1;
    }
    else {
        b = 0;
    }
    if(j<v2.size()) {
        r2 = v2[j];
        c = 1;
    }
    else {
        c = 0;
    }
    if((b==0)&&(c==0)) { }
    else {
        if(b==0) {
            while(j<v2.size()) {
                r2 = v2[j];
                ans += r2.y;
                j++;
            }
        }
        else {
            if(c==0) {
                while(i<v1.size()) {
                    r1 = v1[i];
                    ans += r1.y;
                    i++;
                }
            }
            else {
                if(r1.x!=r2.x) {
                    if(r1.y<r2.y) {
                        ans += r1.y;
                        v2[j].y = r2.y - r1.y;
                        i++;
                        ans = vremia(i,j,ans,v1,v2);
                    }
                    else {
                        if(r1.y>r2.y) {
                            ans += r2.y;
                            v1[i].y = r1.y - r2.y;
                            j++;
                            ans = vremia(i,j,ans,v1,v2);
                        }
                        else {
                            if(r1.y==r2.y) {
                                //ans += r1.y;
                                i++;
                                j++;
                                ans = vremia(i,j,ans,v1,v2);
                            }
                        }
                    }
                }
                else {
                    int k = i+1;
                    b = vremia(k,j,ans,v1,v2) + r1.y;
                    int l = j+1;
                    c = vremia(i,l,ans,v1,v2) + r2.y;
                    if(b<=c) {
                        ans = b;
                    }
                    else {
                        ans = c;
                    }

                }
            }
        }
    }
    return ans;
}

Суть в том, что на некоторых входных данных выдает неправильный ответ( Хотя и редко). Например при входе:
4
3 1 1 3 3 2 1
4 1 1 2 3 4 1 3 1
выдает ответ 5, хотя мин время работы 6

не могу найти, где ошибка в алгоритме, помогите пожалуйста

Tieswar

Дата 29.5.2016, 14:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.5.2016
Где: Томск

Репутация: нет
Всего: нет

У меня на этот ввод выдаёт 3.
Вы бы добавили комментариев к коду. Чтобы хотя бы общие черты логики были видны сразу, без погружения в код.

Это сообщение отредактировал(а) Tieswar - 29.5.2016, 14:34

Tieswar

Дата 29.5.2016, 15:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 29.5.2016
Где: Томск

Репутация: нет
Всего: нет

Немного подредактировал ваш код.

Код


#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct Para
{
    int x;
    int y;
    Para(int t=0,int s=0):x(t),y(s) {}
};



int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2);

int main(int argc, char **argv)
{

    int n, // число станков
        a1,// число пар для первой работы
        a2,// число пар для второй работы
        b, c, i, j;

    // Считываем входящие данные
    ifstream fin("/home/timur/res/texts/input.txt");
    fin >> n;

    vector<Para> v1,v2;
    int ans = 0;
    Para r1,r2;

    // считываем количество пар и добавляем их к первой работе
    fin >> a1;
    for(j = 0; j < a1; j++)
    {
        fin >> b;
        fin >> c;
        Para q(b,c);
        v1.push_back(q);
    }

    // считываем количество пар и добавляем их ко второй работе
    fin >> a2;
    for(j = 0 ; j < a2; j++)
    {
        fin >> b;
        fin >> c;
        Para q(b,c);
        v2.push_back(q);
    }
    i=0;
    j=0;

    // подсчитываем минимальное время работы
    ans = vremia(i,j,ans,v1,v2);
    // Записываем результаты, закрываем файлы, выходим
    ofstream fout("/home/timur/res/texts/output.txt");
    fout << ans;
    fout.close();
    fin.close();
    return 0;
}// main()








int vremia(int i,int j,int ans,vector<Para> &v1,vector<Para> &v2)
{
    int b,c;
    Para r1,r2;

    if(i<v1.size()){

        r1 = v1[i];
        b = 1;

    }else{

        b = 0;
    }//if else

    if(j<v2.size()){

        r2 = v2[j];
        c = 1;

    }else{

        c = 0;

    }//if else

    if((b==0)&&(c==0)){
        cerr << "b == 0 and c == 0\n";
    }else{

        if(b==0){

            while(j<v2.size()){
                r2 = v2[j];
                ans += r2.y;
                j++;
            }//while

        }else{
            if(c==0){
                while(i<v1.size()){
                    r1 = v1[i];
                    ans += r1.y;
                    i++;
                }//while
            }else{

                if(r1.x!=r2.x){

                    if(r1.y<r2.y){

                        ans += r1.y;
                        v2[j].y = r2.y - r1.y;
                        i++;
                        ans = vremia(i,j,ans,v1,v2);

                    }else{

                        if(r1.y>r2.y){

                            ans += r2.y;
                            v1[i].y = r1.y - r2.y;
                            j++;
                            ans = vremia(i,j,ans,v1,v2);
                        }else{
                            if(r1.y==r2.y){

                                //ans += r1.y;
                                i++;
                                j++;
                                ans = vremia(i,j,ans,v1,v2);

                            }//if

                        }//if else

                    }//if else

                }else{

                    int k = i+1;
                    b = vremia(k,j,ans,v1,v2) + r1.y;
                    int l = j+1;
                    c = vremia(i,l,ans,v1,v2) + r2.y;

                    if(b<=c){

                        ans = b;

                    }else{

                        ans = c;

                    }//if else

                }//if else

            }//if else

        }//if else

    }//if else

    return ans;
}

Похоже, просто всегда срабатывает условие в функции рассчёта времени

Код


    if((b==0)&&(c==0)){
        cerr << "b == 0 and c == 0\n";

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »