1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 const int N=1e5+11; 5 int n,h[N],a[N],ans[N]; 6 int sta[N],top; 7 8 inline int re_ad() { 9 char ch=getchar(); int x=0,f=1; 10 while(ch<‘0‘ || ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } 11 while(‘0‘<=ch && ch<=‘9‘) x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar(); 12 return x*f; 13 } 14 15 signed main() 16 { 17 n=re_ad(); 18 for(int i=1;i<=n;++i) h[i]=re_ad(),a[i]=re_ad(); 19 top=0; memset(sta,0,sizeof(sta)); 20 for(int i=1;i<=n;++i) { 21 while(h[sta[top]]<=h[i] && top) --top; 22 ans[sta[top]]+=a[i]; 23 sta[++top]=i; 24 } 25 top=0; memset(sta,0,sizeof(sta)); 26 for(int i=n;i>=1;--i) { 27 while(h[sta[top]]<=h[i] && top) --top; 28 ans[sta[top]]+=a[i]; 29 sta[++top]=i; 30 } 31 int maxx=0; 32 for(int i=1;i<=n;++i) maxx=max(maxx,ans[i]); 33 printf("%lld\n",maxx); 34 // system("pause"); 35 return 0; 36 }
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e4+11,Tree_Sz=5e4+11; 4 int n,m,c; 5 6 struct Point { 7 int x,y; 8 bool operator < (const Point &B) const { 9 return (x==B.x)?y<B.y:x<B.x; 10 } 11 }a[N]; 12 13 inline int re_ad() { 14 char ch=getchar(); int x=0,f=1; 15 while(ch<‘0‘ || ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } 16 while(‘0‘<=ch && ch<=‘9‘) x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar(); 17 return x*f; 18 } 19 20 struct SegmentTree { 21 struct Node { 22 int val,tag; 23 }t[Tree_Sz]; 24 inline void Init() { 25 memset(t,0,sizeof(t)); 26 } 27 inline void Pushup(int d) { 28 t[d].val=max(t[d<<1].val,t[d<<1|1].val); 29 } 30 inline void Pushdown(int d,int l,int r) { 31 t[d<<1].tag+=t[d].tag; 32 t[d<<1|1].tag+=t[d].tag; 33 t[d<<1].val+=t[d].tag; 34 t[d<<1|1].val+=t[d].tag; 35 t[d].tag=0; 36 } 37 void modify(int d,int l,int r,int x,int y,int z) { 38 if(x<=l && r<=y) { t[d].tag+=z,t[d].val+=z; return ; } 39 Pushdown(d,l,r); 40 int mid=(l+r)>>1; 41 if(x<=mid) modify(d<<1,l,mid,x,y,z); 42 if(y>=mid+1) modify(d<<1|1,mid+1,r,x,y,z); 43 Pushup(d); 44 } 45 inline void Modify(int x,int y,int z) { 46 modify(1,1,n,x,y,z); 47 } 48 inline int Query() { 49 return t[1].val; 50 } 51 }st; 52 53 inline bool check(int d) { 54 st.Init(); 55 for(int i=1,j=1,ed;i<=m;++i) { 56 ed=max(1,a[i].x-d+1); 57 st.Modify(max(1,a[i].y-d+1),a[i].y,1); 58 while(a[j].x<ed) st.Modify(max(1,a[j].y-d+1),a[j].y,-1),++j; 59 if(st.Query()>=c) return true; 60 } 61 return false; 62 } 63 64 int main() 65 { 66 c=re_ad(),m=re_ad(); 67 for(int i=1;i<=m;++i) a[i].x=re_ad(),a[i].y=re_ad(),n=max(n,max(a[i].x,a[i].y)); 68 sort(a+1,a+m+1); 69 int l=1,r=n,ans=n+1; 70 while(l<=r) { 71 int mid=(l+r)>>1; //printf("mid: %d\n",mid); 72 if(check(mid)) r=mid-1,ans=mid; 73 else l=mid+1; 74 } 75 printf("%d\n",l); 76 return 0; 77 }
三分做法：
1 #include<bits/stdc++.h> 2 #define double long double 3 using namespace std; 4 const int N=1e5+11; 5 const double St=1e12*1.0,eps=1e-8; 6 int n; 7 8 struct Node { 9 double t,v; 10 bool operator < (const Node &B) const { 11 return t<B.t; 12 } 13 }a[N]; 14 15 double Calc(double d) { 16 double maxx=0.0,minn=St,tmp; 17 for(int i=1;i<=n;++i) { 18 tmp=a[i].v*(d-a[i].t); 19 maxx=max(maxx,tmp),minn=min(minn,tmp); 20 } 21 return maxx-minn; 22 } 23 24 int main() 25 { 26 scanf("%d",&n); 27 for(int i=1;i<=n;++i) cin>>a[i].t>>a[i].v; 28 sort(a+1,a+n+1); 29 double l=a[n].t,r=St; 30 while(r-l>eps) { 31 double mid1=l+(r-l)/3,mid2=r-(r-l)/3; 32 // printf("%.8Lf %.8Lf %.8Lf %.8Lf %.8Lf\n",l,r,mid1,mid2,r-l); 33 if(Calc(mid1)<Calc(mid2)) r=mid2; 34 else l=mid1; 35 } 36 printf("%.2Lf\n",Calc(l)); 37 // if(n==2) printf("%.8Lf %.8Lf %.8Lf %.8Lf\n",a[1].t,a[1].v,a[2].t,a[2].v); 38 return 0; 39 }