XTU 1262 Fish(优先队列+贪心)

钓鱼
http://202.197.224.59/exam/index.php/problem/read/id/1262
题目描述

小明很喜欢钓鱼，现在有n个池塘可以钓鱼，第i个池塘首次内能钓到ai条鱼。 第i个池塘如果被钓过k次，那么每次下一次能钓到的鱼的数目为max{0,ai−k×bi}。 现在小明能钓m次鱼，请问他最多能钓到多少条鱼？

输入

第一行是一个整数T(1≤T≤100)，表示样例的个数。
每个样例的第一行是n(1≤n≤1000),m(1≤m≤100000)；
以后的n行，每行是ai(1≤ai≤10000),bi(0≤bi≤10000)。

输出

每行输出一个样例的结果。

样例输入

2
3 5
3 1
4 2
1 0
2 5
2 1
1 1
样例输出

12
4
样例解释

第一个样例，在第1个池塘钓3次，第2个池塘钓2次，3+2+1+4+2 = 12；
第二个样例，在第1个池塘钓2次，第2个池塘钓1次，2+1+1 = 4。

思路：
维护一个优先队列，使价值最高的鱼优先级最高，钓出这种鱼后，从队首弹出这种鱼，改变价值后再压入，这样便能保证每次钓到的鱼都是价值最高的。

#include <bits/stdc++.h>

using namespace std;

struct node
{
    int a,b;
    friend bool operator <(node A,node B)//价值高的优先级高
    {
        return A.a<B.a;
    }
};
priority_queue<node>pq;
int main()
{
    int t,n,m,a,b;
    scanf("%d",&t);
    while(t--)
    {
        while(!pq.empty())
            pq.pop();
        scanf("%d%d",&n,&m);
        node now;
        while(n--)
        {
            scanf("%d%d",&a,&b);
            now.a=a;
            now.b=b;
            pq.push(now);
        }
        int ans=0;
        while(!pq.empty())
        {
            now=pq.top();
            pq.pop();

            if(now.b==0)
            {
                ans+=now.a*m;
                m=0;
                break;
            }
            else
            {
                ans+=now.a;
                now.a = max(0,now.a-now.b);
                m--;
                pq.push(now);
            }
            if(!m)break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Problem: 1262       User: 2016551517
Memory: 1416K       Time: 1531MS
Language: G++       Result: Accepted

转载请注明出处^ ^