مسئله ای سی ام

[sataho]

‬سلام
این یه مسئله ی ای سی ام بود ، البته می دونم خیلی سادست ولی من هنوز نتونستم حلش کنم . اگه کسی بتونه کمکم کنه ممنون میشم
فرض کنید که هر چه اختلاف قد اسکی باز با چوب اسکی او کمتر باشه، سرعتش بیشتر میشه . حالا ما طول قدهای بازیکن هامون را در آرایه ی h و طول چوب ها را در l داریم . می خوایم جوری چوب ها را انتخاب کنیم که مجموع اختلاف قد هر بازیکن و چوبش مینیمم بشه .
:گیج::متفکر:

[مسعود اقدسی فام]

‬سلام
این یه مسئله ی ای سی ام بود ، البته می دونم خیلی سادست ولی من هنوز نتونستم حلش کنم . اگه کسی بتونه کمکم کنه ممنون میشم
فرض کنید که هر چه اختلاف قد اسکی باز با چوب اسکی او کمتر باشه، سرعتش بیشتر میشه . حالا ما طول قدهای بازیکن هامون را در آرایه ی h و طول چوب ها را در l داریم . می خوایم جوری چوب ها را انتخاب کنیم که مجموع اختلاف قد هر بازیکن و چوبش مینیمم بشه .
:گیج::متفکر:

سوال خیلی ساده رو ای سی ام نمی‌دن! شاید مسابقات تمرینی قبلش باشه.

منظور از مجموع اختلاف قد هر بازیکن و چوبش چیه؟ می‌شه نمونه ارائه بدید؟ اصولا مسابقه‌ی ای سی ام برای هر مساله نمونه ورودی و خروجی رو هم می‌گه.

[sataho]

منظورم این بود که نسبت به خیلی از مسائل ای سی ام آسونه - البته راه حل جستجوی کاملش را می دونم ولی به نطرم خیلی مسخره میاد اگه با اون راه حل تایم نخوره.
یعنی یه آرایه h داریم یه آرایه ی L (با طول مساوی) حالا می خوایم به هر عنصر از h یه عنصر از L را نسبت بدیم ( یعنی جایگشت ) که
sigma |h[i]-L[i]| is minimum
نمونه ی ورودی
3
200 185 190
189 203 186

خروجی
2 1 3

[qwerty11]

طول آرایه حداکثر چنده !؟

مطمئنی مرتب کردن 2 تا آرایه جواب درست رو نمیده !؟ :متفکر: به نظر میاد که اینطور باشه :لبخند:

[sataho]

بعید می دونم این طوری باشه !
فراموش نکنیم که توی ای سی ام نباید گول سمپل ها را بخوریم.
:قهقهه:

[qwerty11]

جواب سوال بالامو ندادی ! طول آرایه حداکثر چنده !؟

بعید ندون ! چون به نظر من که اینجوریه...

به هر حال اگر این روش جواب نداد و n حداکثر نزدیکای 100 اینا بود میتونی از Maximum Weighted Matching استفاده کنی. اینجا یه مقاله ی عالی دربارش وجود داره : http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

[sataho]

هیچ صحبتی از حداکثرn نشده .
اما من توی تست کیس ها بیستر از 120 تا ندیدم.

با چه منطقی مرتب کردن جواب میده ؟ آیا این ادعا قابل اثباته ؟