HDU4355--Party All the Time,HDU3714--Error Curvese三分法

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4355

                                     http://acm.hdu.edu.cn/showproblem.php?pid=3714

       二分法针对于线性判断，适用于单调队列，一旦题目的意思不是单调的，而是类似于二次函数，二分法就派不上用场了，这时候需要三分法。话不多说，直接看代码。

//4355

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
struct point
{double x;double w;
}sp[50005];
int n;
double calc(double k)//算法的核心设计，根据题目意思
{double sum=0;for(int i = 1; i <= n; i++)sum += abs((sp[i].x-k)*(sp[i].x-k)*(sp[i].x-k))*sp[i].w;return sum;
}
int main()
{int t, cases;scanf("%d", &t);for(cases = 1; cases <= t; cases++){scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%lf %lf", &sp[i].x, &sp[i].w);double mid, midmid, esp = 1e-9;double c1, c2;double left = sp[1].x, right = sp[n].x;while(left+esp < right)//三分法的模版套样{mid = (left+right)/2;midmid = (mid+right)/2;c1 = calc(mid);c2 = calc(midmid);if(c1 >= c2) left = mid;else right = midmid;}printf("Case #%d: ", cases);printf("%.0lf\n", c1);}return 0;
}

//3714

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define INF -99999999
struct point{
int a;
int b;
int c;
}abc[10005];
int n;
double calc(double x)
{double temp, s = INF;for(int i = 1; i <= n; i++){temp = abc[i].a*x*x + abc[i].b*x +abc[i].c;if(temp > s)s = temp;}return s;
}
int main()
{int t;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d%d%d", &abc[i].a, &abc[i].b, &abc[i].c);double left = 0, right = 1000, mid, midmid;double c1, c2, esp = 1e-9;while(left+esp < right){mid = (left+right) / 2;midmid = (mid+right) / 2;c1 = calc(mid);c2 = calc(midmid);if(c1 >= c2) left = mid;else right = midmid;}printf("%.4lf\n", c1);}return 0;
}