[JSOI2007]建筑抢修(贪心+后悔)

吐槽

这是一道经典的贪心后悔的题目

做过贪心加后悔的题目的应该一眼可以看出来

解题思路

首先按倒塌时间T2排序，再从1枚举到n，能修就修，发现不能修就从前面找一个修的最慢的来后悔，当然，前提是这个最慢的要比现在要修的慢，不难证明这样肯定更优(节省了时间修后面的)。嗯，做完了，没了，代码实现基本没难度

还有，用堆来维护前面修过的最大值。

一般这类题都是堆吧......(具体情况具体讨论)

code(没注释QwQ)

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iomanip>

#include<algorithm>

#include<ctime>

#include<queue>

#include<stack>

#include<vector>

#define rg register

#define il inline

#define lst long long

#define ldb long double

#define N 150050

using namespace std;

const int Inf=1e9;

int n,ans;

struct HOUSE{

    int fixt,badt;

    bool operator<(rg HOUSE a)

        {

            return badt<a.badt;

        }

}ljl[N];

priority_queue<int>Q;

il int read()

{

    rg int s=0,m=0;rg char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}

    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();

    return m?-s:s;

}

int main()

{

    n=read();

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

        ljl[i]=(HOUSE){read(),read()};

    rg int now=0;

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

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

    {

        if(now+ljl[i].fixt>ljl[i].badt)

        {

            if(!Q.empty())

                if(ljl[i].fixt<Q.top())

                {

                    now-=Q.top()-ljl[i].fixt;

                    Q.pop();

                    Q.push(ljl[i].fixt);

                }

        }

        else

        {

            now+=ljl[i].fixt;

            Q.push(ljl[i].fixt);

        }

    }

    while(!Q.empty())ans++,Q.pop();

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

    return 0;

}

巴特西

[JSOI2007]建筑抢修(贪心+后悔)

[JSOI2007]建筑抢修(贪心+后悔)

吐槽

解题思路

code(没注释QwQ)

最新文章

热门文章