第一题题目描述：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 24 8 65 18 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 31 2 32 3 43 2 1输出1数据范围：n,m<1000 思路：求|s1*2-sum|的最小值，其中sum为整个矩阵的和首先预处理矩阵前缀和，从而O(1)地求子矩阵的和考虑在每个位置上，枚举正方形的边长，可以O(n3)地求解；在枚举正方形的边长时，可以用二分查找来快速找到最小值点，整体复杂度O(n2*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;}