CSPJ T2求调(贪心)
查看原帖
CSPJ T2求调(贪心)
491648
法外狂徒_张三楼主2023/10/22 11:11
#include<bits/stdc++.h>
using namespace std;
int v[100001];
long long ans;
int n,d;
int a[100001];
long long sumv[100001];
int find_lower_price(int st)//找到更低的“低谷”
{
	for(int i=st+1;i<=n;i++)
	{
		if(a[i]<a[st])
		{
			return i;
		}
    }
    return n; 	
}

int main()
{
   // freopen("road.in","r",stdin);
    //freopen("road.out","w",stdout);
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n-1;i++)
    {
		scanf("%d",&v[i]);
		sumv[i]=sumv[i-1]+v[i];//虽然但是没用的前缀和
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int havenv=0;//剩余里程
	for(int i=1;i<n;)
	{
	     int find_out=find_lower_price(i);
	     int totv=sumv[find_out-1]-sumv[i-1];
	     int final_oil=(((totv-havenv)%d==0)?(totv-havenv)/d:((totv-havenv)/d+1));
	    // cout<<totv-havenv<<' ';
	     ans+=final_oil*a[i];
	     havenv=final_oil*d-(totv-havenv);
	     //cout<<havenv<<" ";
	     i=find_out;
	     //cout<<ans<<" "<<i<<endl;
    }	
    printf("%d\n",ans);
	
    return 0;
}
2023/10/22 11:11
加载中...