首页 > 代码库 > BZOJ3203 SDOI2013 保护出题人 凸包+三分法
BZOJ3203 SDOI2013 保护出题人 凸包+三分法
题意：给定N组询问和D，初始时集合为空，每组询问先向集合的开头插入一个元素xi，然后给出一个数pi，求最小的yi使得\[{y}_{i}\left({p}_{i}+D\left(i-1 \right) \right)\geq {x}_{i}\]
题解：设Si=$\sum\limits_{j = 1}^i{x}_{j}$，显然yi=$max\left \{ \frac{{S}_{i}-{S}_{j-1}}{x_{i}+D\left ( i-j \right )} \right \},1\leq j\leq i$，设$a_j=D\cdot j,b_j=S_{j-1}$，那么我们就是要求(ak,bk)使得其与$\left ( x_i+D\cdot i,S_i \right )$的连线斜率最小，显然这个点一定是在一个由(a,b)组成的凸包上，而且斜率的取值一定是一个单峰，三分即可
#include <cstdio>#include <iomanip>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define eps 1e-7#define ll long long#define ld long doubleconst int MAXN=100000+2;struct Point{ ld x,y; Point(){} Point(ld _x,ld _y):x(_x),y(_y){}}Sta[MAXN];int N,Top;ll D,S[MAXN],x;ld Ans;ld Calc(Point a,Point b){ return (b.y-a.y)/(b.x-a.x);}void Insert(Point x){ while(Top>=2 && Calc(Sta[Top-1],Sta[Top])>=Calc(Sta[Top],x)-eps) Top--; Sta[++Top]=x;}ld Find(Point x){ ld lk,rk,Ret=-1; int l=1,r=Top,lm,rm; while(r-l>=3){ lm=(l+l+r)/3,rm=(l+r+r)/3; lk=Calc(Sta[lm],x),rk=Calc(Sta[rm],x); if(lk>rk) r=rm; else l=lm; } for(int i=l;i<=r;i++) Ret=max(Ret,Calc(Sta[i],x)); return Ret;}int main(){ cin >> N >> D; for(int i=1;i<=N;i++){ scanf("%lld %lld",S+i,&x),S[i]+=S[i-1]; Insert(Point(i*D,S[i-1])),Ans+=Find(Point(i*D+x,S[i])); } cout << fixed << setprecision(0) << Ans << endl; return 0;}
BZOJ3203 SDOI2013 保护出题人 凸包+三分法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。