枚举算法的举例（算法枚举趣题）

枚举算法的举例（算法枚举趣题）关于选打手：不选该x打手的情况为打手不值，也就是有能力比x强，花费还便宜的。按照花费排序。思路：枚举学哪个技能，剩下的钱找哪个打手最值。m k (10e5)给出初始金钱数，问所用的最少的时间。天赋只能学习一个，打手也只能请一位。

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