\\مسألة من مسائل الأولمبياد الأمريكي للمعلوماتية //

[Golden man]

حلب الأبقار
ثلاثة مزارعين ينهضون الساعة الخامسة كل صباح ويتوجهون إلى الحظيرة كي يحلبــوا ثلاث أبقار.
المزارع الأول يبدأ بحلب بقرته في الوقت 300(مقدرا بالثواني بعد الساعة الخامسة صباحاً) وينتهي الساعة 1000.
الثاني يبدأ بحلب بقرته في الوقت 700 وينتهيفي 1200.أما الثالـث يبدأ في 1500 وينتهي في 2100.
أطول مدة لم يتوقف بها العمل كانت 900(عندما بدأ المزارع الأول بالحلب في 300 ثم بدأ الثانـي في 700ثم انتهى الأول في 1000 ثم انتهى الثاني في 1200)أي بدأ الأول وقبل أن ينتهـــــي بدأ الثاني فتكون المدة تساوي (زمن نهاية الثاني-زمن بداية الأول =1200-300 = 900)لاحـــظ أن المدة مابين 300 إلى 1200 كان خلالها مزارع أو أكثريحلب بقرته.لاحظ أن أطول مدة لم يعمل بها أي من المزارعين كانت 300(1500-1200).

ما عليك هو أن تكتب برنامج يختبر يعالج قائمة من الأرقام(التي تعبر عن زمن بداية عمل الفلاح و زمن نهايته) ل N فلاح:1 <= N <= 5000يحلبون N بقرة و أن تحسب(بالثواني):- أطول فترة حلبت فيها على الأقل بقرة واحدة(أطول فترة عمل بها فلاح أو أكثر دون انقطاع)- أطول فترة (بعد بداية الحلب) لم تحلب فيها أبقار(توقف المزارعون بها عن العمل).

الدخل:
سطر أول يحتوي على :
عدد مفرد N
سطر ثاني ...n+1
يحوي: عددين طبيعيين أقل من 100000 زمن البداية و زمن النهاية بعد 0500

مثال الدخل:
3
300 1000
700 1200
1500 2100

مثال الخرج:
900 300

(ملاحظة: هذا يعد من أبسط الأمثلة الممكنة للدخل والخرج).

[SYR_SNIPER]

الحل ^^ : (كانت مسألة معقدة بالنسبة لي والله )
لازم نستخدم مفهوم struct لتصبح المسألة قابلة للحل بطريقة سهلة


#include <iostream>
#include <fstream>
using namespace std;
int main() {
struct A {int start,end;};
A t[5001],tmp;
int num ,i ,cont=0 ,idle=0 ,dif ,Mstrt ,Mend;
ifstream fin ("milk2.in");
ofstream fout ("milk2.out");
fin >> num;
for (i=0 ;i<num ;i++)
fin >> t[i].start >> t[i].end;

for (i=0 ;i<num-1 ;i++) { //Bubble sort
for (int j=0 ;j<num-1 ;j++) {
if (t[j].start > t[j+1].start) {
tmp.start = t[j].start;
tmp.end = t[j].end;

t[j].start = t[j+1].start;
t[j].end = t[j+1].end;

t[j+1].start = tmp.start;
t[j+1].end = tmp.end;
}
}
}
cont = t[0].end - t[0].start;
Mstrt = t[0].start;
Mend = t[0].end;
for (i=1 ;i<num ;i++) {
if (t[i].start > Mend) {

dif = t[i].start - Mend; //Idle time
if (dif >idle) idle = dif;

dif = Mend - Mstrt; //Contin time
if (dif >cont) cont =dif;
Mstrt= t[i].start;
Mend = t[i].end;
}
else if (t[i].end >Mend)
Mend = t[i].end;
}
dif = Mend - Mstrt; //Cont time
if (dif >cont) cont = dif;

fout << cont << ' ' << idle <<endl;
}

[Executioner]

السلام عليكم ورحمة الله وبركاته:

شي جميل بس حابب علق على أخي SYR_SNIPER، حول المسألة، فليس بالضرورة حلها باستخدام الـ struct حتى تكون المسألة سهلة، في طرق ثانية.

بس مشان وضح للشباب انو لس في طرق ثانية.