題目來源：Vjudge 1048506

現在有某英雄要放n(10e9)個技能，有冷卻時間，x秒放一次。

1、m個天賦可以學習，第i個天賦花b[i]塊錢，作用是把冷卻時間直接改成a[i]。

2、可以找個打手。有k個打手可以找，請第i個打手需要花掉d[i]塊錢，他會直接幫你放出c[i]次技能。

m,k (10e5)

給出初始金錢數，問所用的最少的時間。

天賦隻能學習一個，打手也隻能請一位。

思路：枚舉學哪個技能，剩下的錢找哪個打手最值。

關于選打手：不選該x打手的情況為打手不值，也就是有能力比x強，花費還便宜的。按照花費排序。

# include <cstdio> # inelinde <cstdlib> # include <vector> # inelude <cstring> # Enelude <algorithm> using namespace std; typedef long long ll; ll a[100005],b[100005];//b錢,a冷卻時間 ll n,m,k,x,s; //n個技能，m個天賦，k個打手，x秒放一次，s錢數 struct hero { ll c,d;//c次技能，d塊錢 friend bool operator < (hero a,hero b) { return a.d<b.d; } hero(ll _c=0,ll _d=0) { c=_c,d=_d; } }; hero h[100005]; vector <hero> ok; void inp() { ll i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(h,0,sizeof(h)); ok.clear(); scanf("%lld%lld%lld%lld%lld",&n,&m,&k,&x,&s); for(i=1; i<=m; i ) scanf("%lld",&a[i]); for(i=1; i<=m; i ) scanf("%lld",&b[i]); for(i=1; i<=m; i ) scanf("%lld",&h[i].c); for(i=1; i<=m; i ) scanf("%lld",&h[i].d); } void gao() { ll i,now=0; sort(h 1,h 1 k); ok.push_back(hero(0,0)) for(i=1; i<=k; i ) { if(h[i].c<=now) continue; now=max(now,h[i].c); ok.push_back(h[i]); } } ll les(ll p) { //二分查找 return(*(--upper_bound(ok.begin(),ok.end(),hero(0,p)))).c; } ll calc() { ll i,t,ans=99999999999999999999; a[0]=x,b[0]=0; for(i=0; i<=m; i ) if(s>=b[i]) { if(n-les(s-b[i])>0) t=(n-les(s-b[i]))*a[i]; else t=0; ans=min(ans,t); } printf("%lld\n",ans); } void work{ inp(); gao(); calc(); } int main(void) { ll t; //需要計算的英雄數 scanf("%lld",&t); while(t--) work(); }

,