//在单调递增数列a中查找>=x的数中最小的一个 while(l<r) { int mid=(l+r)/2; if(a[mid]>=x) r=mid; else l=mid+1; } return a[l]; //在单调递增数列a中查找<=x的数中最大的一个 while(l<r) { int mid=(l+r+1)/2; if(a[mid]<=x) l=mid; else r=mid-1; } return a[l];
//向左取值 while(l<r) { int mid=(l+r)>>1; if(a[mid]>=x) r=mid; else l=mid+1; } //向右取值 while(l<r) { int mid=(l+r+1)>>1; if(a[mid]<=x) l=mid; else r=mid-1; }
//实数域上的二分 eps=1e-(k+2);//k为需要保留的位数. while(l+eps<r) { double mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } while(l+eps<r) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; }
printf("%.3lf ",o);//记得配上printf的输出
这个只能死记了...
见题吧：
很显然的一个二分，答案单调性就不再过多阐述了；
那我们就直接来考虑如何判断答案是否合法.
我们二分出一个平均值后，怎么判断呢？？？
直接说思路吧，将原数组都减去平均值，之后判断是否有合法数列和为0即可。
至于怎么找出合法数列的最大值，用单调队列维护...
对于我来说，就要记住printf....
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=101000; int n,s,t,head,tail; double sum[N],b[N],ans,o; struct gg { ll id; double s; }q[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline bool check(double x) { memset(b,0,sizeof(b)); memset(q,0,sizeof(q));head=tail=0;ans=-1e18; for(register int i=1;i<=n;i++) b[i]=sum[i]-i*x; for(register int i=s;i<=n;i++) { while(head<=tail&&b[i-s]<=q[tail].s) --tail; q[++tail].id=i-s;q[tail].s=b[i-s]; while(head<=tail&&q[head].id<i-t) ++head; ans=max(ans,b[i]-q[head].s); } if(ans>=0) return true; else return false; } inline void erfen() { double l=-10000,r=10000; while(l+1e-5<r) { double mid=(l+r)/2; if(check(mid)) o=l=mid; else r=mid; } } int main() { freopen("1.in","r",stdin); n=read();s=read();t=read(); for(register int i=1;i<=n;i++) sum[i]=sum[i-1]+read(); erfen(); printf("%.3lf ",o); return 0; }
见一道水题吧：
我的暴力果然卡不过...
任务量最大的同学擦得最小值，最大最小，二分答案...
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=301000; int n,m,s[N],a[N]; priority_queue<pair<int,int> >q; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline bool check(int x) { ll ans=0; for(register int i=1;i<=m;++i) { if(a[i]%x==0) ans+=a[i]/x; else ans+=a[i]/x+1; } if(ans>n) return false; else return true; } int main() { freopen("1.in","r",stdin); n=read();m=read(); for(register int i=1;i<=m;++i) a[i]=read(); int l=1,r=1e9; while(l<r) { int mid=(l+r)>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%d",l); return 0; }
...