京东笔试9.2

第一题

题意

给三个区间 可以任意取两个区间 选择两个同时在两个区间内的数 求和最大，如果不存在输出-1

题解

枚举区间组合，每个组合如果区间有交集，则答案是min(r1,r2)，维护答案最大

第二题

题意

给n个商品和m个优惠券，每个商品有价格，每个优惠券有价格限制b和减免金额c，表示在买价格大于等于b的商品时可以减免c元。每个优惠券使用次数不限，求买n个商品最小花费。

题解

注意到如果价格低的商品可以使用一张优惠券，那么价格比他高的商品也都可以使用它。对商品价格和优惠券按价格排序，从小到大枚举每件商品，维护当前可用优惠券的最大减免金额。都是线性的，可以O(n)

第三题

题意

给一个n×m的矩形网格图，每个格子有正权值。可以取一个正方形的区域，计算正方形区域内权值的和与正方形外权值和的差值绝对值。求这个差值的绝对值最小是多少。n m范围1e3

题解

预处理全图前缀和可以O(1)计算给定正方形面积。

枚举矩形的每个网格点作为正方形左上角，以这个网格点作为左上角的正方形可能的答案一定出现在正方形内权值和刚好在全矩形权值和一半的边界处。正方形内权值和对于边长是单调的，因此可以二分边长，找到刚好小于等于矩形总权值和的一半的正方形边长l。用l和l+1的边长维护总答案。枚举每个网格点复杂度n^2，二分查找复杂度log(n)，每次计算O(1)，总复杂度n^2logn

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int a[1000 + 10][1000 + 10];
int n,m;
ll pre[1000 + 10][1000 + 10];
ll cal(int x, int y, int l){
    if(x+l-1>n || y+l-1>m){
        return -1;
    }
    return pre[x+l-1][y+l-1]-pre[x+l-1][y-1]-pre[x-1][y+l-1]+pre[x-1][y-1];
}
ll ABS(ll x){
    if (x<0)return -x;
    return x;
}
int main() {
    scanf("%d%d",&n,&m);
    ll sum = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            sum = sum + a[i][j];
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
        }
    }
    ll now = 0;
    ll ans = sum;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int l = 1,r = min(n-i+1,m-j+1);
            int res=1;
            while(l<=r){
                int mid = (l+r) /2;
                now = cal(i,j,mid);
                if(now<0||sum-now-now<0){
                    r = mid-1;
                }else{
                    res = mid;
                    l = mid+1;
                }
            }
            now = cal(i,j,res);
            ans = min(ans, ABS(now+now-sum));
            now = cal(i,j,res+1);
            if(now > 0){
                ans = min(ans, ABS(now+now-sum));
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}