小根堆85pts求调
查看原帖
小根堆85pts求调
470299
fang20081114楼主2024/7/27 12:40
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll; 
ll n,d;
ll v[maxn],pr[maxn],sum[maxn];
priority_queue<ll,vector<ll>,greater<ll> > q;
int main(){
//	freopen("road.in","r",stdin);
//	freopen("road.out","w",stdout); 
	ll maxs=0;
	scanf("%lld%lld",&n,&d);
	sum[0]=0;
	for(int i=1;i<n;i++)
		scanf("%lld",&v[i]),sum[i]=sum[i-1]+v[i];
	for(int i=0;i<n;i++)
		scanf("%lld",&pr[i]);
	ll ans=0,cnt=-1,s=0,cur=0;
	q.push(pr[0]);
	while(s<v[1]) s+=d,ans+=pr[0];
	ll t=q.top();
	while(cnt<=n&&s<sum[n-1]){
		if(s>sum[cnt+1]){
			++cnt;
			q.push(pr[cnt]);
			if(t!=q.top()){
				t=q.top();
				cur=cnt;
			}
		}else{
			s+=d;
			ans+=pr[cur];
		}
	}
	cout<<ans;
	return 0;
}
2024/7/27 12:40
加载中...