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
Регистрация: 08.03.2016
Сообщений: 0
|
Участники форума уже создавали что то похожее, обратите внимание Задача на С++ Задача по С + + Задача по С++ Задача на С++ Задача на С. |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|