[关闭]
@TaoSama 2016-04-20T02:33:25.000000Z 字数 1535 阅读 1613

每周一题

二分搜索



  1. int l = 1, r = n;
  2. while(l <= r){ //[ ]
  3. int m = l + r >> 1;
  4. if(x > a[m]) l = m + 1;
  5. else r = m -1;
  6. }









  1. //upper_bound > , -1
  2. int binarySearch(int l, int r){
  3. int L = l;
  4. while(l <= r){
  5. int m = l + r >> 1;
  6. int zero = prefixSum[m]-prefixSum[L-1]; //[L,m]
  7. if(zero <= k) l = m + 1;
  8. else r = m - 1;
  9. }
  10. retrun l - 1;
  11. }
  12. //<
  13. pair<int, int> ans = make_pair(-INF, -INF); //长度,左端点
  14. for(int l = 1; l <= n; ++l){
  15. int r = binarySearch(l, n);
  16. ans = max(ans, make_pair(r - l + 1, l));
  17. }
  18. //correct some mistakes
  19. for(int i = ans.second; ans.first--; ++i) a[i] = 1;
  20. for(int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);

  1. int zero = 0;
  2. pair<int, int> ans = make_pair(-INF, -INF); //长度,左端点
  3. // [l, r)
  4. for(int l = 1, r = 1; l <= n; ++l){
  5. while(r <= n && zero + (a[r] == 0) <= k) zero += a[r++] == 0;
  6. ans = max(ans, make_pair(r - l, l));
  7. zero -= a[l] == 0;
  8. }
  9. //correct some mistakes
  10. for(int i = ans.second; ans.first--; ++i) a[i] = 1;
  11. for(int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);



  1. multiset<int> s; //erase(val), (iterator)
  2. int ans = 0;
  3. for(int l = 1, r = 1; l <= n; ++l){
  4. while(r <= n){
  5. if(!s.size()){ //空的
  6. s.insert(a[r++]);
  7. }
  8. else{
  9. //最大值 最小值
  10. if(a[r] - *s.begin() > k || *s.rbegin() - a[r] > k) break;
  11. s.insert(a[r++]);
  12. }
  13. ans += r - l;
  14. if(ans >= MOD) ans -= MOD;
  15. s.erase(s.find(a[l]));
  16. }
  17. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注