المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۰:الگوریتم ها:سوال ۲

فایل‌ها

$n$ فایل داریم که طول $i$‌ ام برابر $l_i$ و تعداد دفعاتی که آن را می‌خوانیم برابر $f_i$‌است. این فایل‌ها روی یک نوار پشت سر هم نوشته می‌شوند. این نوار دارای یک هد است. برای خواندن فایل $i$ ام، هد باید از ابتدای نوار تا انتهای فایل $i$ ام حرکت کند و سپس به ابتدای نوار برگردد.

می‌خواهیم مجموع مسافتی که هد برای خواندن این فایل‌ها طی می‌کند، کمینه شود. الگوریتمی ارائه دهید که بهترین ترتیب قرار دادن فایل‌ها روی نوار را پیدا کند و در ضمن این الگوریتم از لحاظ مرتبه‌ی زمانی بهترین باشد. (درستی و بهینه بودن مرتبه‌ی الگوریتم خود را اثبات کنید.)


ابزار صفحه