题意:一个人有把耐久度为m(1<=m<=10^9)的刀,面对n(1<=n<=10^5)个敌人,杀死 i 敌人需要消耗刀ai耐久度,掉落参数为bi(0<=bi<=10)
的刀,敌人死后留下的刀可以杀死bi个敌人而不费耐久度,问能最多杀多少人,且杀最多人的时候耐久度消耗最小的值。
题解:将敌人分成两类,一类是bi为0,一类不为0,只要能杀死一个bi不为0敌人就能得到所有的bi。
分两种情况:1 只杀bi=0的敌人,这种情况排序从ai小的开始杀即可;
2 先把bi>0 && ai 最小的那个人杀死,然后其他人按照ai从小到大排序用耐久度杀,如果剩余人数<sum(bi)那么剩下的人用bi就可以杀死,
最后得到最优解。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> #include <memory.h> #include <algorithm> #define MIN(a , b) ((a) < (b) ? (a) : (b)) using namespace std; const int inf = 1 << 29; const int maxn = 100002; struct sword { int a,b; bool operator < (const sword &other) const { return a < other.a; } }guai[maxn],tmp; int m,n; inline void in(int &a) { char ch; while(ch = getchar(), ch < '0' || ch > '9'); a = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') { a = a * 10 + ch - '0'; } return; } void solve() { in(n),in(m); int num = 0,cost = inf,sum = 0; int bj = -1,val = inf; for(int i=0;i<n;i++) { in(guai[i].a),in(guai[i].b); sum += guai[i].b; if(guai[i].b > 0 && guai[i].a < val) { val = guai[i].a; bj = i; } } tmp = guai[bj]; guai[bj] = guai[n-1]; guai[n-1] = tmp; if(m >= tmp.a) { sort(guai,guai+n-1); int left = m - tmp.a; int cnt = 1; for(int i=0;i<n-1;i++) { if(n-1-i <= sum) break; if(left >= guai[i].a) { cnt++; left -= guai[i].a; } else break; } cnt += MIN(sum , n-1); num = cnt; cost = m - left; } sort(guai,guai+n); int cnt = 0,left = m; for(int i=0;i<n;i++) { if(guai[i].b != 0) continue; if(guai[i].a <= left) { left -= guai[i].a; cnt++; } else break; } if(num < cnt || (cnt == num && m - left < cost)) { num = cnt; cost = m - left; } printf("%d %d\n",num,cost); return; } int main() { int cas; scanf("%d",&cas); for(int i=1;i<=cas;i++) { printf("Case %d: ",i); solve(); } return 0; }