P4053 [JSOI2007]建筑抢修堆贪心

思路：堆贪心

提交：1次

题解：

先按时间\(sort\)，然后如果能修就直接扔堆里，不能修取堆顶比一下时间长短，把时间短的扔进堆；

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#define ull unsigned long long

#define ll long long

#define R register int

using namespace std;

#define pause (for(R i=1;i<=10000000000;++i))

#define In freopen("NOIPAK++.in","r",stdin)

#define Out freopen("out.out","w",stdout)

namespace Fread {

static char B[1<<15],*S=B,*D=B;

#ifndef JACK

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

#endif

inline int g() {

    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;

    if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;

} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}

inline void gs(char* s) {

    register char ch; while(isempty(ch=getchar()));

    do *s++=ch; while(!isempty(ch=getchar()));

}

} using Fread::g; using Fread::gs;

namespace Luitaryi {

const int N=150010;

struct node { ll w,t;

    inline bool operator <(const node& that) const {return t<that.t;}

}a[N];

int n,cnt;

ll tot;

priority_queue<ll> q;

inline void main() {

    n=g(); for(R i=1;i<=n;++i) a[i].w=g(),a[i].t=g();

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

    for(R i=1;i<=n;++i) {

        if(a[i].w+tot>a[i].t) {

            if(a[i].w<q.top()) {

                tot-=q.top(),q.pop();

                tot+=a[i].w,q.push(a[i].w);

            }

        } else tot+=a[i].w,q.push(a[i].w),++cnt;

    } printf("%d\n",cnt);

}

}

signed main() {

    Luitaryi::main();

}

2019.07.22

巴特西

P4053 [JSOI2007]建筑抢修堆贪心

思路：堆贪心

提交：1次

题解：

最新文章

热门文章

巴特西

P4053 [JSOI2007]建筑抢修 堆贪心

思路：堆贪心

提交：1次

题解：

最新文章

热门文章

P4053 [JSOI2007]建筑抢修堆贪心