ای سی ام کار تازه وارد

لینک سوال

مفهوم سوال

سوال میگه ما N تا شهر داریم و می خوایم یه مرکز تلویزیون بسازیم که به همه شهرها خدمت رسانی کنه.

شهرها همه روی یک خط مستقیم واقع شدند. مختصات هر شهر و جمعیت شون رو داریم.

میزان نارضایتی مردم شهر i رو حاصلضرب جمعیت شهر در فاصله شهر تا مرکز تلویزیون تعریف می کنیم.

میزان نارضایتی کل، مجموع نارضایتی همه شهرهاست.

سوال از ما می خواد که یه نقطه رو برای مرکز تلویزیون انتخاب کنیم که میزان نارضایتی مینیمم باشه.

N < 15000

حل

ادعا می کنیم که مرکز تلویزیون باید روی یکی از شهرها ساخته بشه.

فرض خلف: فرض کنیم نقطه ای بین 2 شهر وجود داشته باشه که مجموع نارضایتی ها تا اون نقطه از دو شهر همجوار کمتر باشه.

شهرهای اطراف رو x, y و نقطه میانی رو a بنامیم. همچنین فرض کنید x < a < y باشه.

مجموع حاصلضرب جمعیت در فاصله هر نقطه قبل از x تا x رو S_x بنامیم. همچنین مجموع حاصلضرب جمعیت در فاصله نقاط بعداز y تا y رو S_y بنامیم.

مجموع جمعیت نقاط کمتر و مساوی x رو T_x و مجموع جمعیت نقاط بزرگتر یا مساوی y رو T_y بنامیم.

میزان نارضایتی نقطه a میشه :

dis(a) = S_x + S_y + |xa| * T_x + |ya| * T_y

اگر T_x برابر با T_y باشه، میزان نارضایتی در نقطه x و a با هم برابره ؛ که این با فرض کمتر بودن نارضایتی در نقطه a در تناقضه.

پس باید T_x مخالف T_y باشه. بدون کاسته شدن از کلیت میشه فرض کرد که T_x < T_y باشه.

تو این حالت میشه دید که هرچه |ya| کمتر باشه میزان نارضایتی کمتر میشه، لذا تو نقطه y کمترین نارضایتی رو داریم. که با فرض کمترین بودن در نقطه a در تناقضه.

لذا مرکز تلویزیون باید روی یکی از شهرها باشه.

حالا کافیه برای هر شهر میزان نارضایتی رو پیدا کنیم.

برای این کار کافیه از چپ به راست نقاط رو بررسی کنیم.

میزان نارضایتی مردم زمانیکه مرکز در X₁ قرار داشته باشه رو حساب می کنیم.

حالا اگه مرکز تلویزیون رو از X_i به X_i+1 منتقل کنیم، میزان نارضایتی میشه:

dis(X_i+1) = dis(X_i) - Total(X_i+1,N) * |X_i+1-X_i| + total(1,X_i) * |X_i+1-X_i|

منظور از (total(x,y یعنی، مجموع جمعیت از شهر x تا شهر y.

نقطه ای که مینیمم این مقادیر رو داشته باشه میشه جواب مساله.