HDU – 4355 Party All the Time 三分

Party All the Time 三分

Source

HDU - 4355

My Solution

题意：每个spirit有一个位置xi一个全中w[i]，如果确定聚会地点为s，则i的花费是 fabs(s - x[i]) ^ 3 * w[i]，求总花费。

三分

对位置xi进行三分，即把区间分为长度相等的三段，进行查找，这样的查找称为三分查找，三分查找通常用来迅速确定最值。

复杂度 略大于 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 5e4 + 8;
const double EPS = 1e-4;

double x[MAXN], w[MAXN];
int n;

inline double getsum(double s)
{
    double res = 0, tmp;
    for(int i = 0; i < n; i++){ tmp = fabs(s - x[i]); res += tmp*tmp*tmp*w[i]; } return res; } int main() { #ifdef LOCAL freopen("1.txt", "r", stdin); //freopen("1.out", "w", stdout); #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); //HDU OJ 突然这句话失效了，迷之TLE很多次，改成scanf和printf就突然过了， ⊙﹏⊙‖∣ int T, i, kase = 1; double l, r, ll, rr, ans1, ans2; //cin >> T;
    scanf("%d", &T);
    while(T--){
        l = 1e6 + 8, r = -(1e6 + 8);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
            scanf("%lf%lf", &x[i], &w[i]);
            l = min(l, x[i]);
            r = max(r, x[i]);
        }
        while(l + EPS < r){ ll = l + (r - l) / 3; rr = r - (r - l) / 3; ans1 = getsum(ll); ans2 = getsum(rr); if(ans1 > ans2){
                l = ll;
            }
            else r = rr;
        }
        ans1 = min(ans1, ans2);
        printf("Case #%d: %.0fn",kase,ans1);
        kase++;
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx