题目链接：点击打开链接
题意:
有n个人去竞拍一件商品，下面给出n个区间表示每个人出的价是区间中随机的一个数（概率均等)
则第一名需要付的钱是第二名的竞拍价格（允许并列第一名）
求支付的钱的期望。
思路:
枚举付的钱，然后求付这个钱的概率，，相乘后求和即可。
对于确定支付x元
分类讨论一下：
1、第一名出价大于x
枚举第一名，然后剩下来的人至少一个人出x元，其他人出<=x，
P(剩下来的人一个人出x元，其他人出<=x) = P(剩下来的人出价<=x) – P(剩下的人出价<x)
2、第一名出价等于x，则出价中至少有2个x
P(至少2人出x) = P(所有人出价<=x) – P(所有人出价<x) – P(恰好有一人出价=x，其他人<x)
#include <stdio.h> #include <string.h> #include <set>#include <map>#include <algorithm>#include <iostream>#include <vector>#include <string>#include <cmath>template <class T>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 <class T>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; //他的出价<=xbool 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++){//第二名出价为ians += work(i) * i; //第一名出价大于ians += work2(i) * i;//第一名出价=i}printf("%.10f\n", ans);}return 0;}
只是微笑地固执自己的坚持，
