[CSP-J 2023] 公路 5pts 悬关求调
  • 板块灌水区
  • 楼主AnOIer
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/16 14:02
  • 上次更新2024/9/16 17:30:26
查看原帖
[CSP-J 2023] 公路 5pts 悬关求调
1036897
AnOIer楼主2024/9/16 14:02
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+100;
int d[MAXN],p[MAXN],sum[MAXN];
signed main() {
	int n,dis;
	cin>>n>>dis;
	for(int i=1;i<n;i++) {
		cin>>d[i];
		sum[i+1]=sum[i]+d[i];//前缀和算路程 
	}
	for(int i=1;i<=n;i++) {
		cin>>p[i];
	}
	int begin=1,end,minp,len=0;
	//begin是起点,end是终点,len是路程长度 
	int oil=0,price=0,k=0;
	//oil是油,price是钱
	for(int i=1;i<=n;i++) {
		minp=p[begin];
		for(int j=begin;j<=n;j++) {
			if(minp>p[j]) {
				end=j;
				minp=p[j];
				break;
			}
		}//找下一个点 
		len=sum[end]-sum[begin];
		int tmp=ceil((len-k)*1.0/dis);
		//要买的油
		oil+=tmp;
		k+=tmp*dis-len;//多出来的 
		price+=tmp*p[begin];
		//cout<<begin<<" "<<end<<" "<<len<<" "<<tmp<<" "<<k<<"\n";
		begin=end;
		if(begin==n) break;
	}
	printf("%d",price);
	return 0;
}
/*
5 4
10 10 10 10
9 8 9 6 5
*/

样例能过,悬关,急

2024/9/16 14:02
加载中...