Gym 101257G：24（尺取）

http://codeforces.com/gym/101257/problem/G Gym 101257G

题意：给出n个人，和一个数s，接下来给出每个人当前的分数和输掉的概率。当一个人输了之后就会掉s分。求第i个人当前的分数大于第j个人当前的分数并且比赛结束后第i个人的分数小于第j个人的（i，j）对数的期望。

思路：用尺取的做法，r指针在前面，l指针在后面，从后往前扫，记录一个前缀和lose，代表前面r指针遇到的人输的概率，当扫到val_r - s >= val_l的时候停止r，让l往左扫，期间lose要减掉遇到的人输的概率，因为相同权值的人不会对彼此有贡献，当扫到和原本的权值不同的数停止，加上贡献，贡献为lose*win[l]。但是比赛的时候加了一个离散化，把所有相同权值的点放在一起考虑了，不知道是什么原因错了。重新直接做就A了。想法挺容易，但是有些细节上的东西还是需要仔细把握。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define N 200010
 4 int w[N];
 5 double e[N];
 6 int main() {
 7     int n, s;
 8     scanf("%d%d", &n, &s);
 9     for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
10     for(int i = 1; i <= n; i++) scanf("%lf", &e[i]);
11     double now = 0, ans = 0;
12     int l = n, r = n, sameindex = n;
13     while(l) {
14         while(w[r] - s < w[l] && r) now += e[r--];
15         while(w[l] == w[sameindex] && sameindex) now -= e[sameindex--];
16         while(l > sameindex) ans += (1.0 - e[l--]) * now;
17     }
18     printf("%.9f
", ans);
19     return 0;
20 }