【文文殿下】 [SDOI2013]保护出题人 题解

【文文殿下】 [SDOI2013]保护出题人 题解

题解

我们把伤害-时间图像画出来。然后维护一下僵尸血量的前缀和。最好情况肯定是有一个僵尸恰好死在戴夫家门口。我们把原点到其他n个点的斜率最大的一个累积到答案。

发现每添加一个点，其他所有点的坐标都变了，但是相对位置没有变，所以我们随便维护一个原点位置就行了。

在n个点中寻找的时候，我们维护一个上凸壳，然后随便二分就行了。二分条件是，他左边的斜率小于他的斜率。

#include<bits/stdc++.h>
using namespace std;typedef long long ll;struct qwq{ll x,y;
};
vector<qwq> T;
vector<ll> q;int l,r;
ll basex,basey;
ll n,d,s;
double ans;
double slope(int a,int b) {double tmp1 = (double)T[b].y-T[a].y;double tmp2 = (double)T[b].x-T[a].x;if(a==b) return 0;return tmp1/tmp2;
}
int binarySearch() {int L = l, R = r;while(L<R) {int mid = (L+R)>>1;if(slope(0,q[mid])<slope(0,q[mid+1<=r?mid+1:0])) L = mid+1;else R = mid;}return R;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>size(n<<1);q.resize(n<<1);cin>>basey>>basex;T[1].x=basex,T[1].y=basey;ans+=(double)basey/basex;l=r=1;q[l]=1;for(int i = 2;i<=n;++i) {ll nx,ny;cin>>ny>>nx;s+=ny;T[i].x=basex-(i-1)*d,T[i].y=ny-s;ll ox =T[i].x-nx,oy = -s;T[0].x=ox,T[0].y=oy;while(l<r&&slope(i,q[r])<slope(q[r],q[r-1])) --r; q[++r]=i;int p = binarySearch();ans+=slope(0,q[p]);}cout.precision(0);cout<<fixed<<ans<<endl;return 0;
}

转载于:.html