CSP J T2 求调!悬关
  • 板块灌水区
  • 楼主crzcqh
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/30 18:50
  • 上次更新2023/11/2 10:40:08
查看原帖
CSP J T2 求调!悬关
769006
crzcqh楼主2023/10/30 18:50
#include<bits/stdc++.h>
using namespace std;
int n,d,ans,Now,cnt;
int a[100010],v[100010],Minv[100010]={INT_MAX},Min[100010],t[100010];
int road[100010];
int main(){ 
	cin>>n>>d;
	for(int i=1;i<n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>v[i];
	for(int i=2;i<=n;i++){
		t[i]=t[i-1]+a[i-1];
	}
	for(int i=1;i<=n;i++){
		Minv[i]=Minv[i-1];
		if(Minv[i]>v[i]){
			Minv[i]=v[i];
			Min[i]=i;
		}else Min[i]=Min[i-1];
	} 
	road[++cnt]=n;
	for(int p=n;p>1;){
		p=Min[p-1];
		road[++cnt]=p;
	}
	// Now 表示现在还可以走几公里 
	for(int i=1;i<=cnt/2;i++) swap(road[i],road[cnt-i+1]);
	for(int i=1;i<cnt;i++){
		int len=t[road[i+1]]-t[road[i]];
		if(Now<len){
			int h=ceil(1.0*(len-Now)/d);
			Now+=h*d;
			ans+=h*v[road[i]];
		}
		Now-=len;
	}
	cout<<ans;
	return 0;
}


}


2023/10/30 18:50
加载中...