http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3594

..脑子秀逗了,这水题想半天

按d排序,然后扫一遍,每次把扫到的加到优先队列中(q值大的在前面),然后判断当前已花费的时间是否大于d[i],如果是则说明序列太挤,那么从中删除一个最耗时的就行。

/*0.452s*/
typedef pair<int, int> p2;
#define x first
#define y second
const int mx = int(8e5) + 5;

p2 p[mx];

bool cmp(const p2 &a, const p2 &b)
{
    return a.y < b.y;
}

int solve(int n)
{
    priority_queue<p2> q;
    p2 tmp;
    int i, cnt = 0, sumt = 0;
    For(i, n)
    {
        sumt += p[i].x, ++cnt;
        q.push(p[i]);
        if (sumt > p[i].y) sumt -= q.top().x, --cnt, q.pop();
    }
    return cnt;
}

int main()
{
    int t, n, i;
    SI(t);
    while (t--)
    {
        SI(n);
        For(i, n) SII(p[i].x, p[i].y);
        sort(p, p + n, cmp);
        PI(solve(n));
        if (t) Pn();
    }
    return 0;
}

Comments

comments powered by Disqus