田园将芜胡不归？既自以心为形役，奚惆怅而独悲？悟已往之不谏，知来者之可追。实迷途其未远，觉今是而昨非。
题目链接http://codeforces.com/contest/746/problem/F
cf div2 386,稍微纪念一下，终于变为blue，然而还是2道题的水平！先说一下这次的大体情况吧！这次是什么比赛的同步，一般这个比赛的题目都比较水，就像这次一样，拿下4,5题不是问题！然而普通的div2，就没有这么好的条件了，真是冲分的好机会！这次做了4题，都是读完题，就有思路，稍微思考一下边界条件，然后码代码就可以了！然后，d题怎么也过不去，后来分析是没有仔细思考，一是枚举的方式不太好，二是这种的边界不好处理！然后就去码e题，居然一次就过了，但是后怕system test会挂，后来听说这题的checker有问题，算是水过了！然后再看了看d题，就没时间了！f题和g题，都没有看！
后来看了下f和g题，g题跟以前的一道题目很相似，然后画了画简单例子，码完就过了。f题实在没什么思路！
这里写一下看完f题的想法，或者是为什么无从下手的原因，或者是什么困惑：
1. 数据范围很大，n=2e5,k=1e9，如果考虑用dp的话，这个数据范围不行啊，考虑dp的原因是：因为不知道那些歌曲该取半，哪些不该取半！
2. 看完官方题解和讨论后，感觉上面的考虑就是扯淡，根本一点关联也没有！
原因是：a. 听的歌曲可以从任意位置开始
b. k时间内听得歌曲都必须听，不能跳过（而这点就限制了，解题思路不能往dp方向考虑，而是区间）
c. 最关键的是：这里固定区间，使得收益最大，（每首歌曲的收益都是正数，没有负数和0，而且听的时间减半也不会对收益造成影响），那么收益最大就是听尽可能多的歌曲，那么，很容易得出结论，（这个题目的限制条件，取半的歌曲的数目上限为w），寻找区间，使得区间内听歌时间最大的w个的歌曲取半，这样得到的是这个区间的最大收益值，这样结果很明确，不容考虑各种组合，不需要枚举，不需要dp，（反正这里也不能dp），最优的也就那么一种。
d. 最终的答案就是遍历所有可能这样区间即可，固定左边界，右边界是非递减的，这就可以使用two pointer来做！
3. 接下来就是码代码，知道思想以后，还有一条鸿沟，就是考虑使用什么数据结构，ac了才是王道。
4. 一开始看题，是在想不明白这题的tag是data structure,现在恍然大悟。
5. 思路里面还有一个小细节，删除的时候需要考虑的，这题还是有一定难度的。质量很高！
这里贴一个别人的代码：写的很清晰，简单，漂亮！
1 /* Author haleyk10198 */ 2 /* �@��: haleyk10198 */ 3 #include <bits/stdc++.h> 4 5 #define MOD 1000000007 6 #define LINF (1LL<<60) 7 #define INF 2147483647 8 #define PI 3.1415926535897932384626433 9 #define ll long long 10 #define pii pair<int,int> 11 #define mp(x,y) make_pair((x),(y)) 12 13 using namespace std; 14 15 string itos(int x){ 16 stringstream ss; 17 ss<<x; 18 return ss.str(); 19 } 20 21 int n, m, k, a[200010], b[200010], tt, res, now; 22 23 set<pii> h1, h2; 24 25 int main(){ 26 //freopen("input.txt","r",stdin); 27 //freopen("output.txt","w",stdout); 28 ios_base::sync_with_stdio(false); 29 cin >> n >> m >> k; 30 for(int i = 0; i < n; i++) 31 cin >> a[i]; 32 for(int i = 0; i < n; i++) 33 cin >> b[i]; 34 for(int l = 0, r = 0; r < n; ){ 35 while(tt <= k && r < n){ 36 if(h1.size() < m){ 37 h1.insert(mp(b[r], r)); 38 tt += (b[r] + 1) / 2; 39 } 40 else if(h1.begin()->first < b[r]){ 41 tt -= (h1.begin()->first + 1) / 2; 42 tt += h1.begin()->first; 43 tt += (b[r] + 1) / 2; 44 h2.insert(*h1.begin()); 45 h1.erase(*h1.begin()); 46 h1.insert(mp(b[r], r)); 47 } 48 else{ 49 h2.insert(mp(b[r], r)); 50 tt += b[r]; 51 } 52 now += a[r++]; 53 if(tt <= k) 54 res = max(res, now); 55 } 56 while(tt > k){ 57 if(h1.count(mp(b[l], l))){ 58 tt -= (b[l] + 1) / 2; 59 h1.erase(mp(b[l], l)); 60 if(!h2.empty()){ 61 auto x = *h2.rbegin(); 62 tt -= x.first; 63 tt += (x.first + 1) / 2; 64 h1.insert(x); 65 h2.erase(x); 66 } 67 } 68 else{ 69 tt -= b[l]; 70 h2.erase(mp(b[l], l)); 71 } 72 now -= a[l++]; 73 if(tt <= k) 74 res = max(res, now); 75 } 76 } 77 cout << res << endl; 78 return 0; 79 }