前缀和、差分、二分

#include<stdio.h>
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
const int N=5010;
int n,m;
int s[N][N];//前缀和数组
int main()
{
    scanf("%d%d",&n,&m);
    m=min(m,5001);//最大半径为5001就可以覆盖完全部
    int x,y,W;
    while(n--)
    {
        scanf("%d%d%d",&x,&y,&W);
        x++,y++;//因为前缀和从1开始则把坐标先+1
        s[x][y]+=W;
    }
    for(int i=1;i<=5001;i++)//二维前缀和公式
        for(int j=1;j<=5001;j++)
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    int ans=0;
    for(int i=m;i<=5001;i++)//枚举所有的正方形
       for(int j=m;j<=5001;j++)
             ans=max(ans,s[i][j]-s[i-m][j]-s[i][j-m]+s[i-m][j-m]);//取这个正方形的最大值
    printf("%d\n",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N],b[N];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];//b是a的差分
    ll p=0,q=0;//p是b中的正数，q是b中的负数
    for(int i=2;i<=n;i++)
        if(b[i]>0) p+=b[i];
       else q-=b[i];
    printf("%lld\n",max(p,q));
    printf("%lld\n",abs(p-q)+1);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
double a[N],s[N];
int n,m;
bool judge(double mid)
{
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-mid;//预处理出来a[i]-mid的前缀和
    double mins=0;//定义前1~i-m中的最小值
    for(int i=m;i<=n;i++)
    {
        mins=min(mins,s[i-m]);//更新最小值
        if(s[i]>=mins) return true;//假如这段区间前缀和差值是大于等于0的说明这段区间是满足的
    }
    return false;//反之不满足
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
    double l=1,r=100000;
    while(r-l>1e-5)//比精度多两位
    {
        double mid=(l+r)/2;
        if(judge(mid)) l=mid;//假如满足，则可以扩大
        else r=mid;
    }
    printf("%d\n",(int)(r*1000));
    return 0;
}

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res(1,1);//初始化答案，刚开始只有1这个数，长度是1
        for(int i=2;i<=N;i++)//枚举剩下的数
        {
            int l=0,r=res.size()-1;
            while(l<r)//二分查找小于i的数
            {
                int mid=l+r+1>>1;
                if(compare(res[mid],i)) l=mid;//假如res[mid]<i,说明i在右边
                else r=mid-1;//反之在左边
            }
            res.push_back(i);//把i放在末尾
            for(int j=res.size()-2;j>r;j--) swap(res[j],res[j+1]);//然后把i换到r+1这个位置上
            if(compare(i,res[r])) swap(res[r],res[r+1]);//假如r这个位置比我大，说明在r这个位置
        }
        return res;
    }
};