编程开发习题:消灭兔子(贪心)。
思路:按照Q币升序排序,血量也是升序排序。先用Q币少的去打血量少的,当碰到一个兔子的血量比伤害要高的时候,可以选择曾经用过的伤害高的箭,和当前的箭对比一下两者能否替换,如果能替换就替换掉,不能替换就继续后找。不会实现反观大佬思路,实现起来就很容易了。
按照箭的伤害降序排序,血量也是降序,然后把伤害比血量高的箭都放到优先队列,选择花费最小的,把兔子射死。直到射死所有兔子或者队列空了。
#includeusing namespace std; const int MAXN = 1e5+10; struct node { int d,p; }; node ns[MAXN]; int B[MAXN]; struct compare { bool operator()(const node& a, const node& b) { //原来这里要用大于号才能使优先队列是最小堆啊 return a.p > b.p; } }; bool cmp(const node& a, const node& b) { return a.d > b.d; } int main() { int n,m; ios::sync_with_stdio(false); cin >> n >> m; for(int i = 0; i < n; ++i) cin >> B[i]; sort(B,B+n); for(int i = 0; i < m; ++i) cin >> ns[i].d >> ns[i].p; sort(ns,ns+m,cmp); priority_queue<> ,compare> que; int j = 0; long long res = 0; for(int i = n-1; i >= 0; --i) { while(j < m && ns[j].d >= B[i]) { que.push(ns[j]); ++j; } if(que.empty()) { cout << "No Solution" <