[CF580B]Kefa and Company（滑动窗口）

题目链接：http://codeforces.com/problemset/problem/580/B

某人有n个朋友，这n个朋友有钱数m和关系s两个属性。问如何选择朋友，使得这些朋友之间s最大差距小于d并且钱数是最多。

可以用滑动窗口，将m从小到大，s从大到小排列，这时在一个队列里维护队首和队尾，假如队首和队尾的s差距≥d时，就把队尾扔掉队首入队否则就仅队首入队。此时更新一下当前最大值。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 typedef long long LL;
10 typedef struct Node {
11     int m, s;
12 }Node;
13 const int maxn = 100100;
14 int n, d;
15 Node f[maxn];
16 
17 bool cmp(Node a, Node b) {
18     if(a.m == b.m) return a.s > b.s;
19     return a.m < b.m;
20 }
21 
22 int main() {
23     // freopen("in", "r", stdin);
24     scanf("%d%d",&n,&d);
25     for(int i = 1; i <= n; i++) {
26         scanf("%d%d",&f[i].m,&f[i].s);
27     }
28     sort(f+1, f+n+1, cmp);
29     int r = 1;
30     int cnt = 1;
31     LL ret = 0, cur = 0;
32     for(int l = 1; l <= n; l++) {
33         while(r <= n && f[r].m - f[l].m < d) {
34             cur += f[r].s;
35             r++;
36             cnt++;
37         }
38         ret = max(cur, ret);
39         cur -= f[l].s;
40     }
41     cout << ret << endl;
42     return 0;
43 }