题目
官方题解
T1:
单调栈，单调队列因为认为考场上会写崩所以写了一个十分暴力的方法(线段树)
然后做一做区间覆盖即可
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #define int long long using namespace std; inline int read(){ int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } int k[800001],n,a[800001],tmp[800001],res[800001],ans[800001]; void pushdown(int k,int l,int r){ if(res[k]==-1) return; ans[k<<1]=res[k]; ans[k<<1|1]=res[k]; res[k<<1]=res[k<<1|1]=res[k]; res[k]=-1; return; } int query1(int k,int l,int r,int x,int y){ if(x>y) return 0; if(x<=l&&r<=y) return ans[k]; int mid=l+r>>1,maxn=0; pushdown(k,l,r); if(x<=mid) maxn=max(maxn,query1(k<<1,l,mid,x,y)); if(mid<y) maxn=max(maxn,query1(k<<1|1,mid+1,r,x,y)); ans[k]=max(ans[k<<1],ans[k<<1|1]); return maxn; } int query(int k,int l,int r,int x,int y){ if(x>y) return 2<<30-1; if(x<=l&&r<=y) { return ans[k]; } pushdown(k,l,r); int mid=l+r>>1,minn=2<<30-1; if(x<=mid) minn=min(minn,query(k<<1,l,mid,x,y)); if(mid<y) minn=min(minn,query(k<<1|1,mid+1,r,x,y)); ans[k]=min(ans[k<<1],ans[k<<1|1]); return minn; } void update1(int k,int l,int r,int x,int y,int pos){ if(x>y) return; if(x<=l&&r<=y){ans[k]=res[k]=pos;return;} pushdown(k,l,r); int mid=l+r>>1; if(x<=mid) update1(k<<1,l,mid,x,y,pos); if(mid<y) update1(k<<1|1,mid+1,r,x,y,pos); ans[k]=max(ans[k<<1],ans[k<<1|1]); return; } void update(int k,int l,int r,int x,int y,int pos){ if(x>y) return; if(x<=l&&r<=y){ans[k]=res[k]=pos;return;} pushdown(k,l,r); int mid=l+r>>1; if(x<=mid) update(k<<1,l,mid,x,y,pos); if(mid<y) update(k<<1|1,mid+1,r,x,y,pos); ans[k]=min(ans[k<<1],ans[k<<1|1]); return; } int h[50001],anss[50001],maxv; signed main(){ memset(res,-1,sizeof(res)); n=read(); for(int i=1;i<=n;i++) k[i]=tmp[i]=a[i]=read(),h[i]=read(); sort(tmp+1,tmp+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp; for(int i=1;i<=n;i++){ int t1=query1(1,1,n,a[i]+1,n); anss[t1]+=h[i]; update1(1,1,n,1,a[i],i); } memset(res,-1,sizeof(res)); memset(ans,127/3,sizeof(ans)); for(int i=n;i>=1;i--){ int t1=query(1,1,n,a[i]+1,n); if(t1>=1&&t1<=n) anss[t1]+=h[i]; update(1,1,n,1,a[i],i); } for(int i=1;i<=n;i++)maxv=max(maxv,anss[i]); cout<<maxv; }
T2:
易发现答案是具有单调性的，所以二分判一判即可
时间复杂度:$O(n^2 log n)$
// luogu-judger-enable-o2 #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; inline int read(){ int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } int c,n; int x[1001],y[1001],minn=2<<30-1,xp[1001]; struct node{ int x,y; }st[1001]; bool CHECK(int l,int r,int w){ if(r-l+1<c) return 0; int cnt=0; int yp[1001]; memset(yp,0,sizeof(yp)); for(int i=l;i<=r;i++) yp[++yp[0]]=st[i].y; sort(yp+1,yp+yp[0]+1); for(int i=c;i<=yp[0];i++){ if(yp[i]-yp[i-c+1]<=w) { return 1; } } return 0; } bool cmp(node x1,node x2){return x1.x<x2.x;} bool check(int xx){ int l=1; for(int i=1;i<=n;i++) st[i].x=x[i],st[i].y=y[i]; sort(st+1,st+n+1,cmp); for(int r=1;r<=n;r++){ if(st[r].x-st[l].x>xx){ if(CHECK(l,r-1,xx)) { return 1; } while(st[r].x-st[l].x>xx) l++; } } if(CHECK(l,n,xx)) return 1; return 0; } int main(){ c=read(),n=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(); int l=0,r=10001; while(l<=r){ int mid=l+r>>1; if(check(mid)) minn=min(minn,mid),r=mid-1; else l=mid+1; } cout<<minn+1; }