P4053 [JSOI2007]建筑抢修堆贪心

待我称王封你为后i 2021-11-17 15:32 207阅读 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 条评论，207人围观）

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

相关阅读

相关 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 赞/ 4 阅读

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

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

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

相关 Poj 3287 The Trip, 2007 (简单贪心)

又是被题意玩坏的节奏。题意：把一个包放入另一个包内，使得总共要带的件数最少,就是说大包可以装小包，且一个大包只能装一个小包，但是这个小包可以继续装更小的包。因为相同大小的包

叁歲伎倆/ 2022年09月20日 12:58/ 0 赞/ 42 阅读

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

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

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

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

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

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

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

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

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

相关 BZOJ1030 [JSOI2007] 文本生成器

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

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

相关 [JSOI2007]麻将模拟 BZOJ1028

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

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

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

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

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

相关 P3452 [POI2007]BIU-Offices

[传送门][Link 1] 首先能想到 $n^2$ 的做法枚举所有两点，看看是否有边相连，如果没有说明它们一定要在同一集合，用并查集维护一下就行注意到如果没有边这个条

ゞ浴缸里的玫瑰/ 2021年10月23日 15:22/ 0 赞/ 213 阅读