「BZOJ2216」[POI2011] Lightning Conductor
Description
已知一个长度为n的序列a1,a2,…,an。
对于每个1<=i<=n，找到最小的非负整数p满足 对于任意的j, aj < = ai + p – sqrt(abs(i-j))
Input
第一行n，(1<=n<=500000)
下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)
Output
n行，第i行表示对于i，得到的p
Sample Input
6
5
3
2
4
2
4
5
3
2
4
2
4
Sample Output
2
3
5
3
5
4
3
5
3
5
4
题解
倒腾一下式子得出f[i]=max{a[j]+sqrt(abs(i-j))}-a[i]
为了把绝对值去掉就正反各做一次取最大值
这个式子显然是满足决策单调的
ydc神犇好像写过题解
http://ydcydcy1.blog.163.com/blog/static/2160890402013315391435/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[500005]; double f[500005],g[500005]; struct data{int l,r,p;}q[500005]; double cal(int j,int i) { return a[j]+sqrt(abs(i-j))-a[i]; } int find(data t,int x) { int l=t.l,r=t.r; while(l<=r) { int mid=(l+r)>>1; if(cal(t.p,mid)>cal(x,mid)) l=mid+1; else r=mid-1; } return l; } void dp(double *F) { int head=1,tail=0; for(int i=1;i<=n;i++) { q[head].l++; if(head<=tail&&q[head].r<q[head].l)head++; if(head>tail||cal(i,n)>cal(q[tail].p,n)) { while(head<=tail&&cal(q[tail].p,q[tail].l)<cal(i,q[tail].l)) tail--; if(head>tail) q[++tail]=(data){i,n,i}; else { int t=find(q[tail],i); q[tail].r=t-1; q[++tail]=(data){t,n,i}; } } F[i]=cal(q[head].p,i); } } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); dp(f); for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]); dp(g); for(int i=1;i<=n;i++) printf("%d\n",max(0,(int)ceil(max(f[i],g[n-i+1])))); return 0; } |
计数器 9301091
OI 课件=>
OI 课件=>
黄学长，您好，第32line的r=mid-1不应该是r=mid吗？蒟蒻，求轻喷
每个人有不同的二分写法吧
我发现把=号去掉，然后改成r=mid根本过不了啊，跪求解释
想一想，为什么？
我问了好多人他们说不知道，如果判断了是不是根本不存在解，还是WA，所以我就改成了黄学长这种写法了，他们好像都这样写2分，然后我就这样写了，目前还没有错过。。。