HDU 4355 Party All the Time（三分）
[導(dǎo)讀]題目鏈接：HDU 4355
題面：
Party All the Time
Time Limit: 6000/2000 MS (Java/Others)????Memory Limit: 65536
題目鏈接：HDU 4355
題面：
Party All the Time Time Limit: 6000/2000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5266????Accepted Submission(s): 1625
Problem Description In the Dark forest, there is a Fairy kingdom where all the spirits will go together and Celebrate the harvest every year. But there is one thing you may not know that they hate walking so much that they would prefer to stay at home if they need to walk a long way.According to our observation,a spirit weighing W will increase its unhappyness for S3*W units if it walks a distance of S kilometers.
Now give you every spirit's weight and location,find the best place to celebrate the harvest which make the sum of unhappyness of every spirit the least. ?
Input The first line of the input is the number T(T<=20), which is the number of cases followed. The first line of each case consists of one integer N(1<=N<=50000), indicating the number of spirits. Then comes N lines in the order that x[i]<=x[i+1] for all i(1<=i
Output For each test case, please output a line which is "Case #X: Y", X means the number of the test case and Y means the minimum sum of unhappyness which is rounded to the nearest integer. ?
Sample Input 1 4 0.6 5 3.9 10 5.1 7 8.4 10 ?
Sample Output Case #1: 832 ?
Author Enterpaise@UESTC_Goldfinger ?
Source 2012 Multi-University Training Contest 6
題意：
??? 給定一維上若干點(diǎn)xi，每個點(diǎn)有對應(yīng)的權(quán)值wi，求一個點(diǎn)的位置p，使得sigma? fabs(p-xi)^3*wi最小。
解題：
? 看了網(wǎng)上現(xiàn)有的所有博客，都是直接說是個凸函數(shù)，三分一下就好。求導(dǎo)好像也不直觀，也不知道具體是怎么證明的，姑且認(rèn)為是個開口向上的二次函數(shù)（因?yàn)榍蟮氖亲钚≈?，且直觀上，p的位置肯定是在中間好），那么三分就可以求解了，需要注意的是，這題C++應(yīng)該是會T的，交G++才能過，然后向最近位取舍，應(yīng)該用%.0lf輸出。
?? 【三分性質(zhì)】
??????? 將區(qū)間三等分，取左等分點(diǎn)為lmid,右等分點(diǎn)為rmid，比如此題，二次函數(shù)開口向上，那么就算lmid的函數(shù)值為lv，rmid的函數(shù)值為rmid，比較lv和rv的值，假設(shè)最小值不在lmid和rmid之間，在兩側(cè)，那么lv，rv哪個更小，其對應(yīng)的等分點(diǎn)就更接近最值，故而舍棄大的那邊。倘若，最小值在lmid和rmid之間，那么無論舍棄哪一邊，都不會丟棄最值，同時達(dá)到逼近最值的效果，因?yàn)樽钪翟诤翁?，我們是不知道的，故而和第一種情況相統(tǒng)一，舍棄較大的一邊。
代碼：
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
using namespace std;
double x[50010],w[50010];
int n;
double cal(double y)
{
double tmp,res=0.0;
for(int i=0;ieps)
{
double lmid,rmid,lv,rv;
lmid=(ri-le)/3+le;
rmid=ri-(ri-le)/3;
lv=cal(lmid);
rv=cal(rmid);
if(lv>rv)
le=lmid;
else
ri=rmid;
}
printf("Case #%d: %.0lfn",i,cal(le));
}
return 0;
} 
下載文檔
