程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 513C Second price auction 概率dp 求期望

Codeforces 513C Second price auction 概率dp 求期望

編輯：C++入門知識

Codeforces 513C Second price auction 概率dp 求期望

題目鏈接：點擊打開鏈接

題意:

有n個人去競拍一件商品，下面給出n個區間表示每個人出的價是區間中隨機的一個數（概率均等)

則第一名需要付的錢是第二名的競拍價格（允許並列第一名）

求支付的錢的期望。

思路:

枚舉付的錢，然後求付這個錢的概率，相乘後求和即可。

對於確定支付x元

分類討論一下：

1、第一名出價大於x

枚舉第一名，然後剩下來的人至少一個人出x元，其他人出<=x，

P(剩下來的人一個人出x元，其他人出<=x) = P(剩下來的人出價<=x) - P(剩下的人出價

2、第一名出價等於x，則出價中至少有2個x

P(至少2人出x) = P(所有人出價<=x) - P(所有人出價

#include   
#include   
#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template 
inline void pt(T x) {
	if (x <0) {
		putchar('-');
		x = -x;
	}
	if (x>9) pt(x / 10);
	putchar(x % 10 + '0');
}
using namespace std;
typedef long long ll;
const int N = 35;
int n, a[N], l[N], r[N];
double work(int x){
	double ans = 0;
	for (int i = 1; i <= n; i++){//顯然只有一個第一名，枚舉這個第一名
		if (r[i] < x+1)continue; //他的出價<=x
		bool ok = true, hav = false;
		for (int j = 1; j <= n; j++) if (i != j){
			if (l[j] <= x && x <= r[j])hav = true;
			if (x < l[j])ok = false;
		}
		if (ok == false || hav == false)continue;

		double p = (double)(r[i] - x) / (r[i] - l[i] + 1);	p = min(p, 1.0);
		double len = 1, H = 1;
		for (int j = 1; j <= n; j++) {
			if (i != j && l[j] <= x && x <= r[j]){
				len *= (double)(x - l[j] + 1) / (r[j] - l[j] + 1);
				H *= (double)(x - l[j]) / (r[j] - l[j] + 1);
			}
		}
		len -= H;
		ans += len * p;
	}
	return ans;
}
double work2(int x){
	bool hav = false;
	for (int i = 1; i <= n; i++)if (x < l[i])return 0; else if (l[i] <= x && x <= r[i])hav = true;
	if (hav == false)return 0;

	double all = 1, one = 0, zero = 1;
	for (int i = 1; i <= n; i++){
		if (l[i] <= x&&x <= r[i]){
			all *= (double)(x - l[i] + 1) / (r[i] - l[i] + 1);
			zero *= (double)(x - l[i]) / (r[i] - l[i] + 1);
		}
	}
	for (int i = 1; i <= n; i++){
		if (l[i] <= x&& x <= r[i])
		{
			double tmp = 1.0 / (r[i] - l[i] + 1);
			for (int j = 1; j <= n; j++)
				if (i != j && l[j] <= x && x <= r[j])
					tmp *= (double)(x - l[j]) / (r[j] - l[j] + 1);
			one += tmp;
		}
	}	
	return (all - zero - one);
}
int main(){
	while (cin >> n){
		for (int i = 1; i <= n; i++)rd(l[i]), rd(r[i]);
		double ans = 0;
		for (int i = 1; i <= 10000; i++){//第二名出價為i
			ans += work(i) * i; //第一名出價大於i
			ans += work2(i) * i;//第一名出價=i
		}
		printf("%.10f\n", ans);
	}
	return 0;
}