1029: [JSOI2007]建筑抢修

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1029

用大根堆维护的简单贪心。
先按t2从小到大排序。
按顺序处理：如果当前时间加上t1<=t2，那么t1入堆，答案加一；
否则，如果堆顶元素比t1大，用t1把堆顶元素替换掉。
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int MaxN=150050;

struct building
{
    int t1,t2;
};

int n,now=0,ans=0;
building a[MaxN];
priority_queue<int> q;

bool cmp(building a,building b)
{
    return a.t2<b.t2;
}

int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>a[i].t1>>a[i].t2;
    }
    sort(a,a+n,cmp);
    for (int i=0;i<n;i++)
    {
        if (now+a[i].t1<=a[i].t2)
        {
            q.push(a[i].t1);
            now+=a[i].t1;
            ans++;
        }
        else
        {
            int top=q.top();
            if (top>a[i].t1)
            {
                now=now-top+a[i].t1;
                q.pop();
                q.push(a[i].t1);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

posted on 2013-02-13 21:55 Kiro 阅读(170) 评论(0)  编辑 收藏 引用 所属分类: 衡八oj

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理