[洛谷P3697]开心派对小火车

题目：洛谷P3697

题目大意是有各站停列车（慢车，相邻2站时间A）和特急列车（相邻2站时间B），特急列车在特定站点停靠。

现在加一种快速列车（相邻2站时间C，A>C>B），停靠K站（包括所有特急列车停靠的站点），要求你设计快速列车的停靠站点，好让1号站点的人T分钟能到达的站点数尽可能多。（相邻指编号相邻的两站，如2号站和3号站）

具体见原题目。

我们设特急列车本次停靠点A，和下次停靠点B，再设从A坐慢车最远到达C，可知A到C之间不需要设任何快速站点。

那么就需要在C的后一个站D设快速站点。

我们可以计算出对于每个D点，先做特急车到A点，再做快车到D点。这样以后，用剩下的时间，接着往后坐慢车最远可以坐多远。记时间为$v$。

把所有$v$放到一个大根堆里，每次贪心选择最优站点。

然后以堆顶元素继续如此操作，直到K站设完。

 于是就有了代码。

 

C++ Code:

#include<cstdio>

#include<algorithm>

#include<cctype>

#include <ext/pb_ds/priority_queue.hpp>

using namespace __gnu_pbds;

using std::min;

#define C c=getchar()

#define LL long long

struct heap{

	LL i,succ,rest,v;

	short f;

	bool operator <(const heap& rhs)const{

		if(f!=rhs.f)return f<rhs.f;

		return(v<rhs.v);

	}

}now;

LL a,b,c,n,m,k,t,s[3005],ans=0;

LL readLL(){

	char C;

	while(!isdigit(c))C;

	LL p=0;

	while(isdigit(c)){

		p=p*10+c-'0';

		C;

	}

	return p;

}

priority_queue<heap>d;

int main(){

	n=readLL(),m=readLL(),k=readLL(),a=readLL(),b=readLL(),c=readLL(),t=readLL();

	for(int i=1;i<=m;i++)s[i]=readLL();

	for(int i=1;i<m;i++)

	if(t>b*(s[i]-1))d.push((heap){s[i],s[i+1],t-(s[i]-1)*b,min(s[i+1]-s[i],(t-(s[i]-1)*b-1)/a+1),1});else break;

	if(t>b*(n-1))ans++;//最后一个站一定为特急列车站，如果能到则答案直接加1。

	k-=m;

	while(!d.empty()&&k){

		now=d.top();

		d.pop();

		if(!now.f)k--;

		ans+=now.v;

		if(now.v&&now.rest>now.v*c)d.push((heap){now.i+now.v,now.succ,now.rest-c*now.v,min(now.succ-now.i-now.v,(now.rest-now.v*c-1)/a+1),0});

	}

	printf("%lld\n",ans-1);//第一个站为起点，不加入计算。

	return 0;

}　　

此题K<=3000，不用堆应该也能解决