程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 2876 NOI2012 騎行川藏 二分+數學算法

BZOJ 2876 NOI2012 騎行川藏 二分+數學算法

編輯:關於C++

題目大意:給定n段路,每段長度為si,如果在這段路上以vi的速度勻速行駛,那麼消耗的體力為ki*(vi-v'i)^2*si,求在不超過體力上限情況下的最大速度

我去年買了個表- - 去網上百度了半天一元三次方程的求根公式才發現函數是遞增的- - 百度百科寫的什麼NM破玩應- -

\

好像沒講明白- - MS只要知道拉格朗日乘數法就能差不多搞懂這道題了- -

#include 
#include 
#include 
#include 
#define M 10100
#define INF 1e9
#define EPS 1e-12
using namespace std;
int n;
double E,s[M],k[M],v[M],x[M];
double Calculate(double lambda)
{
	double temp=0;
	for(int i=1;i<=n;i++)
	{
		double l=max(0.0,v[i]),r=INF;
		while(r-l>EPS)
		{
			double mid=(l+r)/2;
			if(2*lambda*k[i]*mid*mid*(mid-v[i])>1)
				r=mid;
			else l=mid;
		}
		x[i]=(l+r)/2;
		temp+=k[i]*(x[i]-v[i])*(x[i]-v[i])*s[i];
	}
	return temp;
}
void Bisection()
{
	double l=0,r=INF;
	while(r-l>EPS)
	{
		double mid=(l+r)/2;
		if( Calculate(mid)>=E )
			l=mid;
		else r=mid;
	}
}
int main()
{
	int i;
	cin>>n>>E;
	for(i=1;i<=n;i++)
		scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);
	Bisection();
	double ans=0;
	for(i=1;i<=n;i++)
		ans+=s[i]/x[i];
	printf("%.10lf\n",ans);
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved