吃零食 csust oj 贪心

吃零食

桌上有n袋零食，不同的零食会有不同的美味程度wi和腐坏程度di，每种零食在一单位时间内美味程度都会下降di，但是不会降到0以下。

qwb每一单位时间可以吃掉一袋零食。现在qwb想要在吃完所有零食后获得的美味度最大。问最大值是多少？

Input

第一行,一个整数n，代表有n袋零食接下来n行，每行2个整数wi和di(1<=n<=100,000)，(0<=wi<=1,000,000,000)，(0<=di<=10,000)

Output

输出一行，最大的美味度。

4
5 3
4 3
5 4
7 5

这个题目是一个贪心，但是还是感觉有点难的，这个题目要对腐烂速度进行贪心，因为腐烂速度代表美味值的损失，

所以我们要尽量选美味值损失少的，但是如果一个零食的美味值已经小于它的腐烂速度了，这个时候就要改变它的腐烂速度。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + ;

struct node

{

    ll w, d, t;

    node(ll w=,ll d=,ll t=):w(w),d(d),t(t){}

    bool operator<(const node &a)const

    {

        if (a.d == d) return a.w > w;

        return a.d > d;

    }

};

int main() {

    int n;

    scanf("%d", &n);

    priority_queue<node>que;

    for (int i = ; i <= n; i++)

    {

        ll w, d;

        scanf("%lld%lld", &w, &d);

        que.push(node(w, d, ));

    }

    ll day = , ans = ;

    while(!que.empty())

    {

        node e = que.top(); que.pop();

        ll num = e.w - (day - e.t)*e.d;

        if (num <= ) continue;

        if (num < e.d) {

            ll w = num, d = num, t = day;

            que.push(node(w, d, t));

            continue;

        }

        ans += num;

        day++;

    }

    printf("%lld\n", ans);

    return ;

}

贪心

巴特西

吃零食 csust oj 贪心

最新文章

热门文章