Технический форум

Технический форум (http://www.tehnari.ru/)
-   Помощь студентам (http://www.tehnari.ru/f41/)
-   -   Задача на C++ (http://www.tehnari.ru/f41/t246689/)

Тавасилек 29.05.2016 11:09

Задача на C++
 
Здравствуйте, помогите, пожалуйста. Есть задача:
Есть 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

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


Часовой пояс GMT +4, время: 15:14.

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.