题意
有nnn个地区和mmm个学生,在第iii个地区时,车上有kik_iki个学生,车内温度(当前城市的温度tit_iti+当前车上的学生kik_iki)不能超过TiT_iTi,否则,赔偿每个学生xix_ixi元,没经过一个地方,要花费costicost_icosti元,求通过nnn个地区所需要的最少花费(车上可以坐无限多的人,每经过一个地方,学生可以不坐在车上)
思路
- 如果当前城市的温度tit_iti高于TiT_iTi,那么不论车上有多少人,都需要进行赔偿,所以让所有的人都上车,进行一次赔偿,花费为costi+xi×mcost_i+x_i\times mcosti+xi×m
- 如果当前城市温度ti+m≤Tit_i+m\leq T_iti+m≤Ti,满足所有人都在车上,并且不需要进行赔偿,所以此时花费为costicost_icosti;
- 如果当前城市温度不超过TiT_iTi,但是当所有人都在车上时,温度超过了TiT_iTi,那么就要讨论是所有人在一辆车上一起通过还是在多辆车上,每辆车带的人数kkk满足k+ti≤Tik+t_i\leq T_ik+ti≤Ti这两种情况哪种花费少
AC代码
/************************************************************************* > File Name: 215D.cpp > Author: WZY > QQ: 2697097900 > Created Time: 2018年12月04日 星期二 18时05分14秒 ************************************************************************/#include#define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define pi acos(-1.0)#define INF 0x7f7f7f7fconst double E=exp(1);const int maxn=1e6+10;const int mod=1e9+7;using namespace std;int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; ll t,T,x,cost; ll ans=0; for(int i=0;i >t>>T>>x>>cost; ll tt=T-t; // 情况一 if(tt<=0) ans+=cost+x*m; // 情况二 else if(tt>=m) ans+=cost; // 情况三 else { ll k=(m+tt-1)/tt; ll res1=cost*k; ll res2=cost+x*m; ans+=min(res1,res2); } } cout< <