注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3203][Sdoi2013]保护出题人  

2015-04-07 20:06:06|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3203: [Sdoi2013]保护出题人

整数三分

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const double eps = 1e-11;
const int N = 1e5+100;
//int scan(){int i=0;scanf("%d",&i);return i;}
ll scan(){
char cc=' ';ll re=0,fh=1;cc=getchar();while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
int dr;
struct Point{double x,y;Point(double a=0,double b=0){x=a;y=b;}}dui[N];
Point operator - (const Point&a,const Point&b){return Point(a.x-b.x,a.y-b.y);}
double Cross(const Point&a,const Point&b){return a.x*b.y - a.y*b.x;}
int n;
ll sum[N],xi[N],d;
double ans;
double getcost(const Point&pi,const Point&now){return (now.y-pi.y)/(now.x-pi.x);}
void solve(int top){
int i,j;
Point now = Point(xi[top]+1.*top*d,sum[top]);
int l=1,r=dr;
while(l+1<r){
int t,tl,tr;
t = (r-l+1)/3;
tl = l - 1 + t;
tr = tl + t;
double ans[2];
ans[0] = getcost(dui[tl],now);
ans[1] = getcost(dui[tr],now);
if(ans[0] + eps < ans[1])
l = tl+1;
else
r = tr-1;
}
double tmp = max(getcost(dui[l],now),getcost(dui[r],now));
// printf("%f\n",tmp);
ans += tmp;
}
int main(){
int i,j;
n = scan();d = scan();
for(i=1;i<=n;i++){
sum[i] = sum[i-1] + scan();
xi[i] = scan();
}
for(i=1;i<=n;i++){
Point p = Point( 1.*i*d, sum[i-1] );
while(dr > 1 && Cross(dui[dr]-dui[dr-1],p-dui[dr-1]) <= eps)dr--;
dui[++dr] = p;
// for(j=1;j<=dr;j++)printf("%.1f ",dui[j].x/d);printf("\n");
solve(i);
}
printf("%.0f\n",ans+eps);
return 0;
}

题解:
need[i] = max((sum[i] - sum[j-1])/(x[i] + d*i - d*j));
Point(sum[i-1],d*i)维护下凸壳,则对于Point( sum[i], x[i] + d*i )斜率单调

  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017