题目来源：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(); }

,