.
题意:给出n个生产者的开始生产时间和成本,和m个消费者的收购价格和收购截至时间,只能指定一个生产者和一个消费者,每天可以倒卖1个零件,问最大收益。
题解:分治
先把这题转换成一个几何问题:给出n个矩形的左下角和m个矩形的右上角,求最大矩形。设左下角点集为L,右上角为U再预处理一下,把那些不可能成为答案的点去掉,最终使得Li.x<Li+1.x且Li.y>Li+1.y。U也一样,只是去掉的点不同。具体看代码。然后设u(i)表示以Li为左下角的最大矩形的右上角的编号。u(i)是递增的,这里证明一下吧:
如图:u(A)=B,所以SOTUB>SCMNO,假如u(D)=C那么就要满足SCQPO>SSBOR,这显然是不成立的。
所以,我们就可以分治来搞:每次我们处理左下角在l1∼r1之间,右上角在l2∼r2之间的最大值,设md=(l1+r1)/2,递归下去找l1∼mdl2∼u(md)和md∼r1u(md)∼r2。这样总共logn层,每层总共遍历一次U,再加上预处理排序的nlogn,总复杂度就是O((n+m)logn)
代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct pnt
{
int x,y;
}a[500010],b[500010];
int cmp(pnt x,pnt y)
{
return x.x==y.x?x.y<y.y:x.x<y.x;
}
int pre(pnt*a,int size,int type)
{
sort(a,a+size,cmp);
static bool del[500010];
memset(del,0,sizeof(del));
if(type==0)
{
int last=0;
for(int i=1;i<size;i++)
{
if(a[i].y>=a[last].y)
del[i]=1;
else
last=i;
}
}
else
{
int last=size-1;
for(int i=size-2;i>=0;i--)
{
if(a[i].y<=a[last].y)
del[i]=1;
else
last=i;
}
}
int nn=0;
for(int i=0;i<size;i++)
if(!del[i])
a[nn++]=a[i];
return nn;
}
long long get(int x,int y)
{
if(b[y].x<a[x].x&&b[y].y<a[x].y)
return 0;
return (long long)(b[y].x-a[x].x)*(b[y].y-a[x].y);
}
long long wk(int l1,int r1,int l2,int r2)
{
if(l1==r1)
return 0;
int md=l1+r1>>1,hh=l2;
for(int i=l2+1;i<r2;i++)
if(get(md,hh)<get(md,i))
hh=i;
return max(max(wk(l1,md,l2,hh+1),wk(md+1,r1,hh,r2)),get(md,hh));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&b[i].x,&b[i].y);
}
n=pre(a,n,0);
m=pre(b,m,1);/*
puts("");
for(int i=0;i<n;i++)
printf("%d %d\n",a[i].x,a[i].y);
puts("");
for(int i=0;i<m;i++)
printf("%d %d\n",b[i].x,b[i].y);
for(int i=0;i<n;i++)
{
int hh=0;
for(int j=0;j<m;j++)
if(get(i,hh)<get(i,j))
hh=j;
printf("%d %d\n",i,hh);
}*/
printf("%lld",wk(0,n,0,m));
}
Gitalking ...