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

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

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

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

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

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<map>

#include<set>

#define eps 1e-6

#define LL long long

#define pii pair<int,int>

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;

}

巴特西

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

最新文章

热门文章