【链接】点击打开链接

【题意】

有一辆火车,它的长度为L,然后假设这辆车现在随机可能地出现在0..D之间,然后假设它已经耗光了油.

问你它需要走的期望距离是多少.

这里要走的距离指的是车里最近的加油站的距离

如果车覆盖了加油站那么它不用动.

一开始给你n个加油站的位置,同时0和D也有一个加油站

【题解】

把这些加油站按照x顺序排(0和D也有加油站);

然后看看x[i+1]和x[i]的间隔temp = x[i+1]-x[i]；

然后如果间隔temp小于等于L,则直接跳过.

否则大于L的话;

则分成两段,在x[i]+L..X[i]+L+(temp-L)/2这一段

(要到左边x[i]那个加油站);

距离从0..(temp-L)/2

因为均匀分布则期望就为(temp-L)/4

然后X[i]+L+(temp-L)/2..x[i]+L+temp-L这一段也同样

(要到右边x[i+1]那个加油站)

也是从0..(temp-L)/2均匀分布

因此期望也是(temp-L)/4

然后这一段长度为(temp-L)/2,则对答案的贡献都为(temp-L)/(2*D)

因此答案递增2*(temp-L)/4 * (temp-L)/(2*D)

也即(temp-L)^2/(4*D);

double会溢出,要用long double

【错的次数】

【反思】

觉得自己的想法没问题,就要想想精度问题了>_<

【代码】

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

#include <map>

#include <queue>

#include <iomanip>

#include <set>

#include <cstdlib>

#include <cmath>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb emplace_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x)

#define oi(x) printf("%d",x)

#define ol(x) printf("%lld",x)

#define oc putchar(' ')

#define os(x) printf(x)

#define all(x) x.begin(),x.end()

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

#define sz(x) ((int) x.size())

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

//mt19937 myrand(time(0));

//int get_rand(int n){return myrand()%n + 1;}

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 1e5;

double D, L;

int n;

double x[N + 10];

int main() {

	//Open();

	//Close();

	ios::sync_with_stdio(0);

	cin >> D >> L >> n;

	rep1(i, 1, n) cin >> x[i];

	x[++n] = 0, x[++n] = D;

	sort(x + 1, x + 1 + n);

	long double ans = 0;

	rep1(i, 1, n - 1) {

		if (x[i + 1] - x[i] - L <= (1e-6)) continue;

		long double temp = x[i + 1] - x[i];

		temp -= L;

		temp /= 2.0;

		ans += (temp*temp) / D;

	}

	cout << fixed << setprecision(10) << ans << endl;

	return 0;

}

巴特西

【CS Round #43 C】Rectangle Partition