T1
维护一个单调栈
#include <iostream> #include <cstdio> #define N 500000 #define rep(a,b,c) for(int a=b;a<=c;++a) #define Rep(a,b,c) for(int a=b;a>=c;--a) using namespace std; typedef long long LL; int n,top,stack[N],num[N]; LL ans,h[N],a[N],R[N]; int main() { cin>>n; rep(i,1,n) { cin>>h[i]>>a[i],num[i]=i; for(;h[stack[top]]<h[i]&⊤top--) { R[i]+=a[num[stack[top]]]; ans=max(ans,R[i]); } stack[++top]=i; } top=0; Rep(i,n,1) { for(;h[stack[top]]<h[i]&⊤top--) { R[i]+=a[num[stack[top]]]; ans=max(ans,R[i]); } stack[++top]=i; } cout<<ans<<endl; return 0; }
T2
二分
二分矩形的边长，然后我们再试着枚举左边界，通过左边界我们就可以知道右边界，同样通过右边界我们也可以知道左边界，然后我们再在通过左右边界来判断里面的糖果数是否足够，当然我们的上下也是有边界的，我们在当前左右所加的这个矩形里，如果糖果数不够c那么直接返回false，反之，我们在来判断一下在这个区间里每个糖果的y坐标排序，然后将这个糖果的y与他的前c个糖果的y比较，如果小于等于mid的话，说明在这样的长度里我们可以找到c个糖果。
#include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; struct node {int x,y;} a[1005]; int C,n,L,R,mid,b[1005],o,i; int cmp(node i,node j) {return i.x<j.x;} int CMP(int i,int j) {return i<j;} bool WORK(int l,int r) { if (r-l+1<C) return false; o=0; for (int i=l; i<=r; i++) b[++o]=a[i].y; sort(b+1,b+o+1,CMP); for (int i=C; i<=o; i++) if (b[i]-b[i-C+1]<=mid) return true; return false; } bool OK(int x) { int l=1; for (int i=1; i<=n; i++) { if (a[i].x-a[l].x>x) { if (WORK(l,i-1)) return true; while (a[i].x-a[l].x>x) l++; } } if (WORK(l,n)) return true; return false; } int main() { freopen("square.in","r",stdin); freopen("square.out","w",stdout); scanf("%d%d",&C,&n); for (i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y); sort(a+1,a+n+1,cmp); L=0; R=10000; mid=(L+R)/2; while (L<=R) { if (OK(mid)) {R=mid-1; mid=(L+R)/2;} else { L=mid+1; mid=(L+R)/2; } } cout<<L+1; return 0; }
T3
解析几何
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const long double INF=(long double)1000000000*10; long double L,R,mid,ans,hh[100005]; int r,rr,i,n,MAX,X,Y,cnt,vv[100005],vv2[100005]; struct node2 {int t; long double l;} s[200005],S[200005]; struct node {int t,v;} t[100005]; int cmp(node i,node j) {return i.v<j.v || i.v==j.v && i.t>j.t;} struct Node {long double x;int y,z;} p[200005]; int CMP(Node i,Node j) {return i.x<j.x;} long double work(int x,long double y) {return (long double)t[x].v*y-hh[x];} int main() { freopen("chase.in","r",stdin); freopen("chase.out","w",stdout); while (1) { scanf("%d",&n); // if (n==0) return 0; MAX=0; for (i=1; i<=n; i++) { scanf("%d%d",&t[i].t,&t[i].v); MAX=max(MAX,t[i].t); } sort(t+1,t+n+1,cmp); int MIN=t[n].t; for (i=n-1; i>=2; i--) { if (t[i].t>MIN) vv[i]=1; else MIN=t[i].t,vv[i]=0; } for (i=1; i<=n; i++) hh[i]=(long double)t[i].t*t[i].v; r=1; s[1].l=MAX; s[1].t=1; s[2].l=INF; vv[n]=0; for (i=2; i<=n; i++) if (!vv[i]) { while (r && work(i,s[r].l)>=work(s[r].t,s[r].l)) r--; if (!r) {r=1; s[1].l=MAX; s[1].t=i; continue;} L=s[r].l; R=s[r+1].l; mid=(L+R)/2.0; for (int I=1; I<=80; I++) { if (work(i,mid)>=work(s[r].t,mid)) {R=mid; mid=(L+R)/2.0;} else {L=mid; mid=(L+R)/2.0;} } s[++r].l=mid; s[r].t=i; s[r+1].l=INF; } rr=1; S[1].l=MAX; S[2].l=INF; S[1].t=n; MIN=t[1].t; for (i=2; i<n; i++) if (t[i].t<MIN) vv2[i]=1; else MIN=t[i].t,vv2[i]=0; for (i=n-1; i>=1; i--) if (!vv2[i]) { while (rr && work(i,S[rr].l)<=work(S[rr].t,S[rr].l)) rr--; if (!rr) {rr=1; S[1].l=MAX; S[1].t=i; continue;} L=S[rr].l; R=S[rr+1].l; mid=(L+R)/2.0; for (int I=1; I<=80; I++) { if (work(i,mid)<=work(S[rr].t,mid)) {R=mid; mid=(L+R)/2.0;} else {L=mid; mid=(L+R)/2.0;} } S[++rr].l=mid; S[rr].t=i; S[rr+1].l=INF; } cnt=0; for (i=1; i<=r; i++) {p[++cnt].x=s[i].l; p[cnt].y=1; p[cnt].z=s[i].t;} for (i=1; i<=rr; i++) {p[++cnt].x=S[i].l; p[cnt].y=0; p[cnt].z=S[i].t;} sort(p+1,p+cnt+1,CMP); X=Y=0; ans=INF; for (i=1; i<=cnt; i++) { if (p[i].y==1) X=p[i].z; else Y=p[i].z; // printf("%.5f ",(double)p[i].x); if (X && Y) ans=min(ans,work(X,p[i].x)-work(Y,p[i].x)); } printf("%.2f ",fabs((double)ans)); return 0; } }