YL杯超級籃球賽

jzoj1325

題目大意

給n個點，每一個點都有一個值（$a_i$）,現在讓你找出一個點，使${\sum }_{i=1}^n(|X?x_i|+|Y?y_i|)\times a_i$最小，輸出此公式的值

輸入樣例

1
1
0 0

輸出樣例

0.00

數據范圍

第一題$N?50000$,x,y都在longint范圍內。

解題思路

我們可以發現x和y沒有任何關系，我們可以拆開來求，然后我們判斷XY在那個位置最優即可（詳情見代碼），有dalao說就是帶權中位數（好像又是）

代碼

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n, s, xl, yl, num, ans, a[50500]; struct rec {ll w, s; }x[50500], y[50500]; bool cmp(rec x, rec y) {return x.w < y.w; } int main() {scanf("%lld", &n);for (ll i = 1; i <= n; ++i){scanf("%lld", &a[i]);num += a[i];}for (ll i = 1; i <= n; ++i){scanf("%lld %lld", &x[i].w, &y[i].w);x[i].s = a[i];//記下權值y[i].s = a[i];}sort(x + 1, x + 1 + n, cmp);//排序sort(y + 1, y + 1 + n, cmp);xl = 1;while (xl < n){s += x[xl].s;while(x[xl + 1].w == x[xl].w)//位置相同的都要加在一起s += x[++xl].s;if (s < num - s) xl++;//往右挪對s各單位有負影響對剩下的有正影響else break;}s = 0;yl = 1;while (yl < n)//同上{s += y[yl].s;while(y[yl + 1].w == y[yl].w)s += y[++yl].s;if (s < num - s) yl++;else break;}for (ll i = 1; i <= n; ++i)ans += abs(x[xl].w - x[i].w) * x[i].s + abs(y[yl].w - y[i].w) * y[i].s;//求總和printf("%lld.00", ans); }

總結

以上是生活随笔為你收集整理的YL杯超级篮球赛（jzoj 1325）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。