Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 29.05.2016, 11:09   #1 (permalink)
Тавасилек
Новичок
 
Регистрация: 29.05.2016
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Задача на 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

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

Старый 29.05.2016, 11:09
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Участники форума уже создавали что то похожее, обратите внимание

Задача на С++
Задача по С + +
Задача по С++
Задача на С++
Задача на С.

Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




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

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.