[JSOI2007]建筑抢修 (贪心)

题目链接

Solution

可以考虑 \(dp\) ,但是很显然 \((n^2)\) 降不下来.

然后考虑贪心,首先,绝对的正确的是,在同等的情况下,给后面的留更多的时间.

首先按照 \(T_2\) 排序.

然后我们维护一个大根堆每修理一栋建筑我们就把这栋建筑的T1值加入堆若当前无法修理我们判断堆顶是否比这栋建筑的T1大如果大取消修理堆顶，改为修理当前建筑.

Code

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+10,inf = 2e9, mod = 1e9+7;

typedef long long ll;

int n;

pair<int ,int > P[N];

int main()

{

    scanf("%d",&n);

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

        scanf("%d%d",&P[i].second,&P[i].first);

    int ans = 0;

    ll tmp = 0;

    sort(P+1,P+n+1);

    priority_queue<int > q;

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

    {

        if(P[i].first>=P[i].second+tmp) q.push(P[i].second),ans++,tmp+=P[i].second;

        else

        {

            if(q.empty()) continue;

            int k = q.top();

            if(k>P[i].second)

            {

                tmp-=k;

                tmp+=P[i].second;

                q.pop();

                q.push(P[i].second);

            }

        }

    }

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

    return 0;

}

巴特西

[JSOI2007]建筑抢修 (贪心)

题目链接

Solution

Code

最新文章

热门文章