Тавасилек |
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
не могу найти, где ошибка в алгоритме, помогите пожалуйста
|