HDU 4355 Party All the Time（三分|二分）-白红宇

HDU 4355 Party All the Time（三分|二分）

阅读量：7244 次

发布时间：2019-06-29

本文共 1240 字，大约阅读时间需要 4 分钟。

题意：n个人，都要去參加活动，每一个人都有所在位置xi和Wi，每一个人没走S km,就会产生S^3*Wi的“不舒适度”，求在何位置举办活动才干使全部人的“不舒适度”之和最小，并求最小值。

思路：首先能够得出最后距离之和的表达式最多仅仅有两个极点，

更进一步仅仅有一个极点，否则无最小值。

那么我们就可用三分法或者二分法求解。即对原函数三分或对导数二分就可以。

#include
     
        #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
           
             #include
             #include
             
               #include
              
                #include
               
                #include
                 #include
                 
                  #define eps 1e-6 #define LL long long #define pii pair
                  
                   using namespace std; const int maxn = 100000+100;//const int INF = 0x3f3f3f3f;double w[maxn], x[maxn];int n;double fx(double x0) { double ans = 0; for(int i = 0; i < n; i++) { ans += pow(fabs(x[i]-x0), 3)*w[i]; } return ans;}double find(double L, double R) { for(int i = 0; i < 30; i++) { double midl = L+(R-L)/3, midr = L+(R-L)*2/3; if(fx(midl) <= fx(midr)) R = midr; else L = midl; } return R;}int main() {// freopen("input.txt", "r", stdin); int T; cin >> T; int kase = 0; while(T--) { cin >> n; double minp = 1000000, maxp = -1000000; for(int i = 0; i < n; i++) { scanf("%lf%lf", &x[i], &w[i]); minp = min(minp, x[i]); maxp = max(maxp, x[i]); }// cout << fx(0) << endl; printf("Case #%d: %d\n", ++kase, (int)(fx(find(minp, maxp))+0.5)); } return 0;}