【codevs2382】挂缀

这个题……服气了
我们假设之前已经选择了\(w\)重量的珠子,现在我们要考虑a挂b上比较优还是b挂a上比较优
b挂a上的时候,\(c_{a} \geq w_{b} + w, c_{b} \geq w\)
a挂b上的时候,\(c_{b} \geq w_{a} + w, c_{a} \geq w\)
所以如果a挂b上比较优的话\(c_{b} – (w_{a} + w) \geq c_{a} – (w_{b} + w)\),既\(c_{b} + w_{b} \geq c_{a} + w_{a}\)
反之\(c_{b} – (w_{a} + w) \leq c_{a} – (w_{b} + w)\),既\(c_{a} + w_{a} \geq c_{b} + w_{b}\)
我们要留尽可能多的承重力挂别的珠缀,这样我们降序排序即可,但是并不好处理。所以我们正着排,如果\(c_{a} \geq w\),就直接往上挂,否则从里面调出一个最重的踢出去就行了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, w, lx, ly, ans;

struct in
{
    lo c, w, s;
}ter[200020];

inline bool cmp(in a, in b)
{
    return a.s < b.s;
}

priority_queue <lo> qwq;

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), ter[i] = (in){lx, ly, lx + ly};
    sort(ter + 1, ter + 1 + n, cmp);
    for(ri i = 1; i <= n; i ++)
    {
        if(w <= ter[i].c)
            w += ter[i].w, ans ++, qwq.push(ter[i].w);
        else
        {
            lo qaq = qwq.top();
            if(qaq > ter[i].w)
                w += ter[i].w - qaq, qwq.pop(), qwq.push(ter[i].w); 
        }
    }
    printf("%lld\n%lld", (lo)qwq.size(), w);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注