Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

二、二分和前缀和_二分前缀和

作者：Cpp五条 | 2024-05-25 06:23:49

踩

二分前缀和

6、P1873 [COCI 2011/2012 #5] EKO / 砍树

7、P1102 A-B 数对

8、P2440 木材加工

10、P2678 [NOIP2015 提高组] 跳石头

二分：

一、二分步骤

确定一个区间，使得目标值一定在区间中
找一个性质，满足性质：一定具有二段性，答案是二段性的分界点。

二、二分类型

1、第一类：ans是红色区间的右端点


int m = l + r / 2;
 
while(l < r)
 
将[l , r]分成[l, m - 1] 和 [m, r]

2、第二类：ans是绿色区间的左端点


int m = l + r / 2;
 
while(l < r)
 
将[l , r]分成[l, m] 和 [m + 1, r]

3、遇到问题思考顺序

二分，dfs，dp，贪心

三、二分例题

1、789. 数的范围


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int main() {
    double l = - 10000;
    double r = 10000;
    double n;
    cin >> n;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if ( mid * mid * mid >= n) { // 比如说 mid = 0,而 0 < 1000,
//所以左边界 = mid,再比如说：mid = 500，而500 * 500 * 500 >= 1000,所以右边界 = mid;
            r = mid;
        }
        else
        l = x;
    }
        printf("%.6lf",l);
   return 0;
}

2、790.数的三次方根


#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
 
int main() {
    vector<int> a;
    int n;
    cin >> n;
    int q;
    cin >> q;
    a.resize(n);
    for (int i = 0; i < n; i ++){
        cin >> a[i];
    }
    int x;
    int l = 0;
    int r = n - 1;
    while (q--) {
        cin >> x;
        while (l < r) {
           int mid = l + r >> 1;
           if (a[mid] >= x) r = mid;
           else
           l = mid + 1;
        }
        if (a[l] == x) {
          cout << l << " ";
        r = n - 1;
        while (l < r) {
           int mid = l + r + 1>> 1;
           if (a[mid] <= x) l = mid;
           else
           r = mid - 1;
        }
        cout << r << endl;
    }
    else
    cout << "-1 -1" << endl;
    }
    return 0;
}

3、730.机器人跳跃问题


#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
 
using namespace std;
const int N=1e5+10;
int h[N],n;
bool check(int mid)//判定能量是否够用 
{
    for(int i = 1; i <= n; i++)
    {
        mid = 2 * mid - h[i]; 
        if(mid < 0) return false; //如果小于，就说明不够用
        else if(mid >= 1e5) return true; // 够用
    }
    return true;
}
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    cin >> h[i];
    int l = 0,r = 1e5;//二分边界 
    while(i < j)
    {
        int mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid + 1;
    }
    cout << l;
    return 0;
}

4、1221. 四平方和


#include<iostream>
using namespace std;
#include<unordered_map>
typedef pair <int ,int > PII;
unordered_map <int, PII> s;
int main()
{
    int n;
    cin >> n;
    int a, b, c, d;
    for (int c = 0 ; c <= n; c ++) 
        for(int d = c; d * d + c * c <= n; d++) {
            int t = c * c + d * d;
            if(s.count(t) == 0) // 记录第一次出现的t和数字，因为是从小到大，所以说一定符合题意
            s[t] ={c, d};
       }
       for (int a = 0 ; a <= n; a ++) 
        for(int b = a; a * a + b * b <= n; b ++) {
              int t = n - a * a + b * b;
              if(s.count(t)) { // 如果这个数不等于0，说明找到了
              cout << a << " "<< b <<" "<< s[t].first<<" "<< s[t].second;
              return 0;
              }
        }
    return 0;
}

5、1227.分巧克力


#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 100010;
 
int n, k;  // 有n块巧克力，k个小朋友
int wid[N], len[N];  // 分别保存巧克力的长和宽
 
// 计算当正方形的边长为u时，总共能分得多少块巧克力
int get_sum(int u) {
  int sum = 0;
  for (int i = 0; i < n; i++) {
    // 巧克力块数
    sum += ((wid[i] / u) * (len[i] / u));
  }
  return sum;
}
 
int main() {
 cin >> n;
 cin >> k;
  for (int i = 0; i < n; i++) {
   cin >> wid[i];
   cin >> len[i];
  }
  // 二分模板
  // 性质是“当边长取mid时，能够分得k块巧克力”
  // 显然在一个数轴上，目标值的左侧（比目标值小的数）都是满足这个性质的，右边则不满足
  // 所以我们要找的值是满足这个性质的最右端
  // 如果当前取的mid满足这个性质，那么l有可能就是我们要找的目标值，所以用l = mid来更新
  // 综上所述，用以下模板
  int l = 0, r = N;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (get_sum(mid) >= k) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  printf("%d\n", l);
  return 0;
}

6、P1873 [COCI 2011/2012 #5] EKO / 砍树


#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 10000100;
int a[N];
bool check(int x) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += max(0,a[i] - x);
        if (sum >= m)
            return true;
    }
    return false;
}
long long sum = 0;
int main() {
    cin >> n >> m;
    int maxt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxt = max(a[i],maxt);
    }
    sort(a + 1, a + 1 + n);
    int i;
    int res = 0;
    int l = 0,r = maxt + 1;
    while (l + 1 < r ){
        int mid = l + r >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    if (check(r)) cout << r << endl;
    else cout << l << endl;
  
    return 0;
}

7、P1102 A-B 数对


#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,c;
const int N = 1000010;
int a[N];
int search1(int x) {
    int l = 0,r = n + 1;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (a[mid] < x) 
            l = mid;
        else
            r = mid;
            
    }
    if (a[r] == x)
        return r;
    else
        return -1;
}
int search2(int x) {
    int l = 0,r = n + 1;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (a[mid] <= x) 
            l = mid;
        else
            r = mid;
            
    }
    if (a[l] == x)
        return l;
    else
        return -1;
}
int main() {
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1,a + 1 + n);
    long long cnt = 0;
    for (int b = 1; b <= n; b++) {
        int A = a[b]+ c;
        int res1 = search1(A);
        if (res1 == -1) 
            continue;
        else {
        int res2 = search2(A);
        cnt += res2 - res1 + 1;
        }
    }
    cout << cnt << endl;
    return 0;
}

8、P2440 木材加工


#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int n,k;
long long sum = 0;
bool check(int x) {
    int sum = 0;
    for (int i = 1; i <= n; i ++) {
        sum += a[i] / x;
        if (sum >= k) return true;
    }
    return false;
}
int main() {
    cin >> n >> k;
    int longest = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        longest = max(a[i],longest);
    }
    int sum = 0;
    int res = 0;
    int l = 0,r = longest;
    while (l + 1 != r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            l = mid;
        }
        else
            r = mid;
    }
    if (check(r)) cout << r << endl;
    else cout << l << endl;
    return 0;
}

10、P2678 [NOIP2015 提高组] 跳石头

前缀和：

一、例题

1、795.前缀和


#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
 
int main() {
    int n, m;
    cin >> n;
    int x;
    cin >> m;
    vector<int> s(n + 10);
    for (int i = 1; i <= n; i++) {
        cin >> x;
        s[i] = s[i - 1] + x;
    }
    int l,r;
    while (m--) {
        cin >> l;
        cin >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

2、796.子矩阵的和


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
#define N 1010
int main() {
    int n, m, q;
    cin >> n;
    cin >> m;
    cin >> q;
    int a[N][N] = {0};
    int s[N][N] = {0};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
         cin >> a[i][j];
           s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    int x1, x2, y1,y2;
    while (q--) {
        cin >> x1 ;
        cin >> y1;
        cin >> x2;
        cin >> y2;
        cout <<  s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]<< endl;
    }
    return 0;
}

3、730.机器人跳跃问题


#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
 
using namespace std;
const int N=1e5+10;
int h[N],n;
bool check(int mid)//判定能量是否够用 
{
    for(int i = 1; i <= n; i++)
    {
        mid = 2 * mid - h[i];
        if(mid < 0) return false;
        else if(mid >= 1e5) return true;
    }
    return true;
}
 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    cin >> h[i];
    int i = 0,j = 1e5;//二分边界 
    while(i < j)
    {
        int mid = i + j >> 1;
        if(check(mid)) j = mid;
        else i = mid + 1;
    }
    cout << j;
    return 0;
}

4、1230.K倍区间


 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
const int N = 100010;
 
int n, k;
LL s[N], cnt[N];
// cnt的意义：存储模k的值，将其作为左端点（模k左端点）的数量
// for的意义：遍历每个端点，先将其作为模k右端点，根据其模k的值查看它有
// 多少个模k左端点，即能形成多少个模k区间，然后将其作为模k左端点，数量加1
// for前cnt[0] = 1的意义：当遍历出首个为k倍的前缀和时，它不需要模k左端点即可形成模k区间，为满足//通解将0作为其模k左端点，故cnt[0] ++
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
 
    LL res = 0;
    cnt[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++ ;
    }
 
    cout << res;
 
    return 0;
}

5、99.激光炸弹


#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 5010;
 
int n, m;
int s[N][N];
 
int main()
{
    int cnt, R;
    cin >> cnt >> R;
    R = min(5001, R);
 
    n = m = R;
    while (cnt -- )
    {
        int x, y, w;
        cin >> x >> y >> w;
        x ++, y ++ ;
        n = max(n, x), m = max(m, y);
        s[x][y] += w;
    }
 
    // 预处理前缀和
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
 
    int res = 0;
 
    // 枚举所有边长是R的矩形，枚举(i, j)为右下角
    for (int i = R; i <= n; i ++ )
        for (int j = R; j <= m; j ++ )
            res = max(res, s[i][j] - s[i - R][j] - s[i][j - R] + s[i - R][j - R]);
 
    cout << res << endl;
 
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/620892

二、二分和前缀和_二分 前缀和

二分：

一、二分步骤

二、二分类型

1、第一类：ans是红色区间的右端点

2、第二类：ans是绿色区间的左端点

3、遇到问题思考顺序

三、二分例题

1、789. 数的范围

2、790.数的三次方根

3、730.机器人跳跃问题

4、1221. 四平方和

5、1227.分巧克力

6、P1873 [COCI 2011/2012 #5] EKO / 砍树

7、P1102 A-B 数对

8、P2440 木材加工

10、P2678 [NOIP2015 提高组] 跳石头

前缀和：

一、例题

1、795.前缀和

2、796.子矩阵的和

3、730.机器人跳跃问题

4、1230.K倍区间

5、99.激光炸弹

二、二分和前缀和_二分前缀和