P4053 [JSOI2007]建筑抢修堆贪心

待我称王封你为后i 2021-11-17 15:32 219阅读 0赞

### 思路：堆贪心 ###

### 提交：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

转载于:https://www.cnblogs.com/Jackpei/p/11227318.html

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关 [JSOI2007]建筑抢修

题目： [JSOI2007]建筑抢修，哈哈，我们今天来看一道贪心算法的题嘛，这是选自JSOI上的一道题，好了，我们一起来看看题意吧：考虑到直接复制题目，或者截屏的方式...

ゝ一纸荒年。/ 2024年04月20日 07:19/ 0 赞/ 78 阅读

相关 JSOI2007 建筑抢修

题目链接：[戳我][Link 1] 开始以为是按照修建时间短的排序，先把修建时间短的修了。但是这样显然有问题，因为可能前面的倒塌时间靠后，你先修了，后面塌的就不...

港控/mmm°/ 2024年04月17日 05:22/ 0 赞/ 69 阅读

相关 P1197-[JSOI2008]星球大战

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

Myth丶恋晨/ 2023年06月01日 08:47/ 0 赞/ 14 阅读

相关 P1094 [NOIP2007 普及组] 纪念品分组——贪心算法

题目描述元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括

秒速五厘米/ 2022年11月12日 04:25/ 0 赞/ 161 阅读

相关 NOIP 2007 纪念品分组(贪心)

题目描述元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件

ゝ一世哀愁。/ 2022年05月16日 02:13/ 0 赞/ 230 阅读

相关洛谷P4165 [SCOI2007]组队(排序堆)

题意 [题目链接][Link 1] Sol 跟我一起大喊：n方过百万，暴力踩标算！一个很显然的思路是枚举\\(H, S\\)的最小值算，复杂度\\(O(n^3

缺乏、安全感/ 2022年03月27日 14:12/ 0 赞/ 221 阅读

相关 1028: [JSOI2007]麻将——模拟（暴力）

1028: \[JSOI2007\]麻将 Description 　　麻将是中国传统的娱乐工具之

亦凉/ 2022年02月01日 13:57/ 0 赞/ 229 阅读

相关 BZOJ1030 [JSOI2007] 文本生成器

我再看错模数我就是呆头考虑包含任意的补集不包含任何然后典型的AC自动机上dp 长度为l不能走到任何关键点特么模数多写了个0 问题是我刚跟zyf吐槽了模数就当考前

朱雀/ 2021年12月23日 06:19/ 0 赞/ 240 阅读

相关 [JSOI2007]麻将模拟 BZOJ1028

题目描述麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东、南、西、北、中、发、白七种）和序数牌（分为条子、饼子、万子三种花色，每种花色各有一到九的九种牌），

柔情只为你懂/ 2021年12月16日 19:59/ 0 赞/ 202 阅读

相关 P4053 [JSOI2007]建筑抢修堆贪心

思路：堆贪心提交：1次题解：先按时间\\(sort\\)，然后如果能修就直接扔堆里，不能修取堆顶比一下时间长短，把时间短的扔进堆； inclu

待我称王封你为后i/ 2021年11月17日 15:32/ 0 赞/ 220 阅读