【bzoj3203】保护出题人

  • 本文为博主原创,未经许可不得转载

好题一道!

测试时专注于此题,然而还是只拿到了暴力分,果然是我弱啊

好吧,我不会凸包。。。。。。

令sumi表示第i个僵尸以及之前的僵尸的体力总和,disi表示第i个僵尸与房屋的初始距离

我们发现我们能消灭一个僵尸当且仅当y>=sumidisi

那么我们要求的显然就是max{sumidisi}

我们将一个僵尸抽象成一个点sumidisi,那么我们发现每个回合僵尸之间的相对位置是不变的

因此我们可以维护一个凸包,三分即可

——来自POPOQQQ

注意:强制转换不能四舍五入,只能输出0位小数了

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
#include<bits/stdc++.h>
#define FILE "plant"
#define MAXN 100010
#define eps 1e-7
using namespace std;
typedef long long ll;
struct node{
ll x,y; node(){}
node(const ll a,const ll b):x(a),y(b){}
}p[MAXN],sta[MAXN];
int n,top;
ll d,a[MAXN],sum[MAXN];
double ans;
inline ll read(){
ll x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
double slop(node a,node b){return (double)(a.y-b.y)/(a.x-b.x);}
void insert(const node &b){
while(top>=2&&slop(sta[top-1],sta[top])>=slop(sta[top],b)-eps) --top;
sta[++top]=b;
}
double find(node b){
int l=1,r=top; double temp=0;
while(l+3<=r){
int mid1=(r-l)/3+l,mid2=(r-l)*2/3+l;
if(slop(sta[mid1],b)>slop(sta[mid2],b)) r=mid2;
else l=mid1;
}
for(int i=l;i<=r;++i) temp=max(temp,slop(sta[i],b));
return temp;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read(); d=read();
for(int i=1;i<=n;++i){
a[i]=read(); sum[i]=sum[i-1]+a[i];
ll x=read(); insert(node(d*i,sum[i-1]));
ans+=find(node(d*i+x,sum[i]));
}
printf("%.0lf\n",ans);
return 0;
}
文章目录
,