二分查找前缀和整理

佚名 / 2024-01-24 / 原文

二分查找与二分答案

第一种就是普通的二分查找就是进行左右边界的判断，其中第一种就是进行往左找，第二种往右找，之后用区间进行判断之后按照片条件进行选择，其中二分查找的最重要的就是有单调性。

/
bool binery_serch1(int x) {
	int l=0,r=n-1;
	while(l<r) {
		mid=l+r>>1;
		if(a[mid]<=x) {
			r=mid;
		} else l=mid+1;
	}
}
bool binery_search2(int x) {
	int l=0,r=n-1;
	while(l<r) {
		int mid=l+r+1>>1;
		if(a[mid]>=x)
			l=mid;
		else r=mid-1;
	}
}

　　二分答案也是非常用的定好区间之后进行直接在区间中进行操作，直接进行check

这个直接用向左找到最小值之后再check里进行找到那个相应的向左找的那个判断

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
// #define int long long
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 1e3 + 10;
int a[N], n, m, ct, idx, now;
int g[M][M], e[M][M];
bool vis[N], st[N];
bool check(int x)
{
    int cnt = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (sum + a[i] <= x)
        {
            sum += a[i];
        }
        else
        {
            sum = a[i];
            cnt++;
        }
    }
    return cnt < m;
}
void solve()
{
    int l = -1, r = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        r += a[i];
        l = max(l, a[i]);
    }
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
}
signed main()
{
    FAST;
    int T = 1;
    // cin>>T;
    while (T--)
    {
        solve();
    }
}

找最大值向右找之后在进行特判区间进行 check里写 l=mid

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define int long long
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10, M = 1e3 + 10;
int a[N], n, m, ct, idx, now;
int g[M][M], e[M][M];
bool vis[N], st[N];
bool check(int x)
{
    int sum = 0;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        ans += a[i] / x;
    }
    return ans >= m;
}
void solve()
{
    int l = 0, r = 0;
    int sum = 0;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        r += a[i];
    }
    if (r < m)
    {
        cout << '0' << endl;
        return;
    }

    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;
}
signed main()
{
    FAST;
    int T = 1;
    // cin>>T;
    while (T--)
    {
        solve();
    }
}

同理这个就是先是有小数但是可以进喜那个相乘之后二分答案进行找到最大值，之后进行找出二分判断条件

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10, M = 1e3 + 10;
int  n, m, ct, idx, now;
int g[M][M], e[M][M];
bool vis[N], st[N];
int a[N];
bool check(int x) {
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans+=a[i]/x;
	}
	return ans >= m;
}
void solve() {
	int l = 0, r = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		double x;
		cin>>x;
		x=(int)(x*100);
		a[i]=x;
	}
	r=10000000;

	while (l < r) {
		int mid = (l + r+1)>> 1;
		if (check(mid))
			l = mid;
		else
			r = mid - 1;
	}
	printf("%.2lf",(r*1.0)/(100.0));
}
signed main() {
	FAST;
	int T = 1;
	// cin>>T;
	while (T--) {
		solve();
	}
}

前缀和

一维前缀和公式

s[i]=s[i-1]+a[i];

计算公式 s[r]-s[l-1];

二维前缀和：

s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]

计算公式

s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define int long long
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 5e6 + 10, M = 1e3 + 10;
int  n, m, ct, idx, now;
int g[M][M], e[M][M];
bool vis[N], st[N];
int a[5010][5010];
int s[5010][5010];
int b[N];
void solve() {
	int R;
	cin>>n>>R;
	R=min(5001,R);
	int x1=R,y1=R;
	for(int i=1; i<=n; i++) {
		int x,y,z;
		cin>>x>>y>>z;x++,y++;
		x1=max(x1,x);
		y1=max(y,y1);
		
		a[x][y]+=z;
	}
	for(int i=1; i<=x1; i++) {
		for(int j=1; j<=y1; j++) {
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	int ans=0;
	for(int i=R; i<=x1; i++) {
		for(int j=R; j<=y1; j++) {
			ans=max(ans,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);

		}
	}
	cout<<ans<<endl;



}



signed main() {
	FAST;
	int T = 1;
	// cin>>T;
	while (T--) {
		solve();
	}
}

　差分

首先是构造差分数组 b[i]=a[i]-a[i-1];

之后进行输入要加入的区间

b[l]+=c,b[r+1]-=c;

最后输出最后结果

a[i]=a[i-1]+b[i]

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 5e6 + 10, M = 1e3 + 10;
int  n, m, ct, idx, now;
int g[M][M], e[M][M];
bool vis[N], st[N];
int a[N];
int s[N];
int b[N];
void solve() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		b[i]=a[i]-a[i-1];
	}
	while(m--) {
		int l,r,c;
		cin>>l>>r>>c;
		b[l]+=c;
		b[r+1]-=c;
	}
	int minn=0x3f3f3f3f;
	for(int i=1; i<=n; i++) {
		a[i]=b[i]+a[i-1];
		minn=min(minn,a[i]);
	}
	cout<<minn<<endl;



}
signed main() {
	FAST;
	int T = 1;
	// cin>>T;
	while (T--) {
		solve();
	}
}