題意：
某A有一個劍 堅韌度為m
他可以用這個劍去攻打別的隊伍
殺掉第 i 個隊伍需要消耗的堅韌度為 Ai 并可以用得到的劍去打別的隊(Bi個)
但是打完別的隊這個劍就不能用了
問怎么用最少的堅韌度擊敗最多的隊伍
?
給出T組樣例
每個樣例給出n m n表示有n個隊
接下來n行給出Ai Bi 表示殺掉這個隊需要消耗的堅韌度和殺掉這個隊可以得到的劍可以殺的隊伍數
輸出可以殺掉的最多的隊和最少花費的堅韌度
?
思路：
可以想到的就是 殺掉一個bi != 0理論上就可以殺掉所有 bi != 0 的隊伍
×××××錯的思路..
把bi != 0 和 bi == 0分成兩組
先用把一個bi != 0里需要用的堅韌度最少的隊伍殺掉..然后用得到的劍殺掉別的bi != 0的隊伍
然后用這些劍去把 bi == 0 的殺掉
當這些得到的劍用完之后就用自己的劍盡量多得把別的隊伍殺掉
×××××反思ing..
這個方法沒考慮到的問題就是
4 2
1 1
1 1
1 0
7 0
這組數據如果用上面的思路
結果就會是 3 1?
而最優解應該是 4 2
問題就出在得到的劍可能不用來殺 bi != 0而用來殺 bi == 0但是需要的堅韌度 ai 大的隊伍
可以得到更好的答案
?
所以
√√√√√√√√√√√√√√√正確的思路
分兩種情況考慮
①. 只殺 bi == 0 的隊伍
②. 殺 bi != 0 和 bi == 0的隊伍
這樣就要考慮有多少個 bi != 0的隊伍是用自己的劍殺的
?
所以應該分兩種情況求值
然后第二種情況就遍歷用自己的劍殺多少個bi == 0 的隊伍
求得最優解
?
Tips：
好吧~我表示我的變量總是弄錯
這道題主要是把 bi == 0 和 bi != 0 分組討論
?
Code：
View Code?
題目鏈接：
)
)
