第一题

题目描述：a有三个区间[l1,r1] [l2,r2] [l3,r3]，a,b在这三个区间内同时选择一个自己喜欢的区间，这两个区间不能相同

接下来a和b需要在自己喜欢的区间内选择一个数，且必须都在对方的区间内，还要使得这两个数的和尽可能大

输入

1 3 2 4 4 6

输出

8

范围：均小于1e9；如果不存在这种值，输出-1

思路：确定ab区间后，每次选交集最大的数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int solve(int a1,int b1,int a2,int b2)
{
	if(b1<a2 || b2<a1)
		return -1;
	return min(b1,b2)*2;
}
int main()
{
	int a1,b1,a2,b2,a3,b3;
	cin>>a1>>b1>>a2>>b2>>a3>>b3;
	cout<<max(max(solve(a1,b1,a2,b2),solve(a1,b1,a3,b3)),solve(a2,b2,a3,b3));
	return 0;
}

第二题

题目描述：小红准备买n件物品，第i件物品的价格是ai。另外，小红有m种优惠券，第i个优惠券是：买一件价格不小于bi的商品时，可以减去ci的价格。每件商品最多只能用一次优惠券。每种优惠券可以使用多次。问买全部商品最少需要多少钱？

输入

3 2

4 8 6

5 1

8 5

输出

12

数据范围：n,m<=200000 ；ai,bi,ci<=1e9

思路：从小到大考虑所有优惠券的bi，那么优惠券的ci也应该递增。因此删去所有无用的优惠券，再找每件商品能用的最大券，这里可以用二分加速

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

const int N=2e5+3;

int n,m;
int a[N];

struct yh{
	int b,c;
	bool operator<(const yh&o)const{
		if(b==o.b)
			return c>o.c;
		return b<o.b;
	}; 
}t[N];

int cnt=0, inc[N];
map<int,int>h;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);

	for(int i=0;i<m;i++)
		scanf("%d%d",&t[i].b,&t[i].c);

	sort(t,t+m);
	int a1=-1, b1=-1;
	for(int i=0;i<m;i++)
		if(t[i].b>a1 && t[i].c>b1)
		{
			a1=t[i].b;
			b1=t[i].c;
			inc[cnt++]=a1;
			h[a1]=b1;
		}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		int*t=upper_bound(inc,inc+cnt,a[i]);
		if(t>inc)
			ans+=a[i]-h[*(t-1)];
		else
			ans+=a[i];
		
	}
	cout<<ans;
	return 0;
}

第三题

题目描述：小红拿到了一个矩形的蛋糕，分成n行m列，共n*m个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度

小红希望切割出一个正方形的小蛋糕（正方形边长必须平行于矩形的边长，且必须都是完整的区域），自己吃掉正方形的部分，把剩下的部分给小紫吃

小红希望两人吃的部分的美味度之和尽可能接近，小红吃的蛋糕美味度之和为s1，小紫吃的蛋糕美味度之和为s2，请输出|s1-s2|的最小值

输入

3 3

1 2 3

2 3 4

3 2 1

输出

1

数据范围：n,m<1000

思路：求|s1*2-sum|的最小值，其中sum为整个矩阵的和

首先预处理矩阵前缀和，从而O(1)地求子矩阵的和

考虑在每个位置上，枚举正方形的边长，可以O(n³)地求解；在枚举正方形的边长时，可以用二分查找来快速找到最小值点，整体复杂度O(n²*logn)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=1e3+2;

int n,m;
int a[N][N];
ll sum_l[N][N], sum[N][N];
ll ans=1e10;

bool check(int x, int y, int r)
{
	ll s1 = sum[x+r-1][y+r-1] -sum[x-1][y+r-1] -sum[x+r-1][y-1] + sum[x-1][y-1];
	return s1*2 < sum[n][m];
}
void solve(int x,int y)
{
	int l=1, r=min(n-x+1,m-y+1),mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(x,y,mid))
			l=mid+1;
		else
			r=mid;
	}
	mid =l;
	
	ll s1,d;
	s1 = sum[x+mid-1][y+mid-1] -sum[x-1][y+mid-1] -sum[x+mid-1][y-1] + sum[x-1][y-1];
	d = s1*2 - sum[n][m];
	if(d<0)d*=-1;
	ans=min(ans,d);

	if(mid>1)
	{
		mid--;
		s1 = sum[x+mid-1][y+mid-1] -sum[x-1][y+mid-1] -sum[x+mid-1][y-1] + sum[x-1][y-1];
		d = s1*2 - sum[n][m];
		if(d<0)d*=-1;
		ans=min(ans,d);
	}

}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
			
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			sum_l[i][j]=sum_l[i][j-1]+a[i][j];

	for(int j=1;j<=m;j++)
		for(int i=1;i<=n;i++)
			sum[i][j]=sum[i-1][j]+sum_l[i][j];
			
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			solve(i,j);
			
	cout<<ans;
	return 0;
}