题解

本题使用贪心算法 + 优先队列求解电车行驶问题。

算法思路：

1. 基本模拟：

   • 对于每个车站 $a[i]$，计算初始状态下电池电量 $init\_val = p - (a[i]-1) \times B$
   • 如果 $init\_val < 0$，说明无法到达该车站，跳过
   • 否则，计算从该车站出发能够行驶的距离：$\min(a[i+1]-a[i], 1 + init\_val / A)$

2. 充电站选择策略：

   • 对于每个车站，计算如果在此处建立充电站能够额外行驶的距离
   • 充电消耗：行驶 $(t-l)$ 个单位距离后充电需要消耗 $(t-l) \times C$ 的电量
   • 充电后可行驶距离：$\frac{init\_val - \min(init\_val, (t-l) \times C)}{A} + 1$
   • 将所有可能的充电收益加入优先队列

3. 贪心选择：

   • 使用**优先队列（大根堆）**维护所有充电方案的收益
   • 每次从队列中取出收益最大的方案
   • 最多选择 $k$ 个充电站

4. 答案计算：

   • 初始答案为不建充电站时能到达的最远距离
   • 加上从优先队列中选出的 $k$ 个最优方案的收益

时间复杂度：$O(m \cdot k + k \log k)$

#include<bits/stdc++.h>
#define LF putchar(10)
#define SP putchar(32)
using namespace std;
typedef long long ll;
typedef long long ui;
const ui N=3005;
template<typename T>void read(T& x)
{
	x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
	while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void readd(T& arg)
{
	double x=0;char ch=getchar();double f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
	while(ch>47&&ch<58){x=x*10.0+(double)(ch&15),ch=getchar();}ch=getchar();
	double e=0.1;while(ch>47&&ch<58){x=x+(ch&15)*e,ch=getchar(),e/=10.0;}arg=x*f;
}
template<typename T,typename... Args>void readd(T& x,Args&... args){readd(x);readd(args...);}
bool check_readc_char(char ch){return (ch>64&&ch<91)||(ch>96&&ch<123);}
template<typename T>void reads(T& x)
{
	char ch=getchar();ui len=0;while(!check_readc_char(ch))ch=getchar();
	while(check_readc_char(ch))x[++len]=ch,ch=getchar();x[len+1]=0;
}
template<typename T,typename... Args>void reads(T& x,Args&... args){reads(x);reads(args...);}
template<typename T>void write(T x){if(x<0){putchar(45);x=-x;}if(x>9)write(x/10);putchar(x%10|48);}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP;write(args...);}}
ui n,m,k,p,A,B,C,a[N],ans;
priority_queue<ui> q;
void solve()
{
	read(n,m,k,A,B,C,p);
	k-=m;
	for(ui i=0;i<m;i++)
	{
		read(a[i]);
	}
	a[m]=n+1;
	for(ui i=0;i<m;i++)
	{
		ui init_val=p-(a[i]-1)*B;
		if(init_val<0)
			continue;
		ans+=min(a[i+1]-a[i],1+init_val/A);
		ui l=a[i],r=a[i+1];
		ui t=a[i]+min(a[i+1]-a[i],init_val/A)+1;
		for(ui j=1;j<=k&&t<r;j++)
		{
			q.push(min(r-t,(init_val-min(init_val,(t-l)*C))/A+(init_val>=(t-l)*C)));
			t+=(init_val-min(init_val,(t-l)*C))/A+1;
		}
	}
	ans--;
	while(q.size()&&k)
		k--,ans+=q.top(),q.pop();
	write(ans);
	LF;
}
int main()
{
//	freopen("wjts.in","r",stdin);
//	freopen("wjts.out","w",stdout);
	solve();
	return 0;
}