首页 > 其他分享 >P4053 [JSOI2007] 建筑抢修

P4053 [JSOI2007] 建筑抢修

时间:2025-01-11 22:43:38浏览次数:1  
标签:std JSOI2007 抢修 修理 房子 second P4053 heap first

题意:n个房子要修理,每个房子有修理时间和限制时间,如果在限制时间内房子没有修理好就报废了,问最多修理好几个房子。
我们贪心的先修限制时间小的,并用一个大根堆存修理时间,如果遇到一个房子修理不了,尝试和之前修理过的房子中修理时间最长的换,这样可以减少总时长,并且也合法,因为换了之后,被影响的那几个房子的开始修理时间会提前。

点击查看代码
void solve() {
	int n;
	std::cin >> n;
	std::vector<std::pair<i64, i64> > a(n);
	for (int i = 0; i < n; ++ i) {
		std::cin >> a[i].first >> a[i].second;
	}

	std::sort(a.begin(), a.end(), [&](std::pair<i64, i64> & a, std::pair<i64, i64> & b) {
		return a.second < b.second;
	});

	std::priority_queue<i64> heap;
	i64 t = 0;
	for (int i = 0; i < n; ++ i) {
		if (t + a[i].first > a[i].second) {
			if (heap.top() > a[i].first && t - heap.top() + a[i].first <= a[i].second) {
				t -= heap.top();
				t += a[i].first;
				heap.pop();
				heap.push(a[i].first);
			}
		} else {
			t += a[i].first;
			heap.push(a[i].first);
		}
	}

	std::cout << heap.size() << "\n";
}

标签:std,JSOI2007,抢修,修理,房子,second,P4053,heap,first
From: https://www.cnblogs.com/maburb/p/18666313

相关文章

  • [luoguP4051/JSOI2007] 字符加密
    题意给定字符串\(s\),输出将\(s\)的所有循环同构的字符串排序后,每个字符串的末尾的字符。sol因为要对循环同构的字符串排序,因此我们可以将\(s\)复制一遍,拼在后面,计算\(sa\),满足\(sa_i\len\)的所有元素的相对位置即为排序后字符串的相对位置,输出即可\(sa\)的计算详见......
  • [题解]P4052 [JSOI2007] 文本生成器
    P4052[JSOI2007]文本生成器正难则反,我们发现用总字符串个数\(26^m\),减去不可读的字符串个数,就是答案。要使一个字符串不可读,就不能让任何模式串在其中出现。如果某个主串的第\(i\)位与自动机的节点\(j\)相匹配,那么如果状态\(j\)包含模式串(即有一个前缀是一个模式串),那么不管主......
  • 【反悔贪心】P2949WorkSchedulingG+P4053[JSOI2007]建筑抢修题解
    这两天遇到了几个很神奇的题目——能反悔的贪心。赶紧记录一下。例1(用时一定模型)用时一定:每个任务完成的耗时都是一样的。题面:Luogu-P2949WorkSchedulingG大体思路是:先把所有任务按照截止时间从小到大排序,然后枚举,遇到一个能做任务的就把他做了,把他的贡献加入一个......
  • 「刷题记录」[JSOI2007] 文本生成器
    第一道AC自动机+DP题。题目链接:P4052[JSOI2007]文本生成器-洛谷|计算机科学教育新生态(luogu.com.cn)利用容斥原理的思想,答案就是所有串的数量减去不可读的串的数量。设\(dp\left(i,j\right)\)表示串长为\(i\),在AC自动机上走到编号为\(j\)时不经过单词结......
  • [JSOI2007]建筑抢修
    [JSOI2007]建筑抢修跟经典题poj1456非常像。首先如果两个都被选入那么截至时间T2小的放前面肯定更优,所以我们先按T2排序。然后逐个遍历建筑,建立一个维修时间为关键字的大根堆,如果前面花费的总时间+维修的时间小于当前的T2,直接加入。否则判断是否小于堆顶,如果小于堆顶则替换,因为......
  • 洛谷P4051 [JSOI2007]字符加密 题解 后缀数组sa的应用
    题目链接:https://www.luogu.com.cn/problem/P4051题目大意:给定一个长度为\(n\)的字符串\(s\),每次将\(s\)的首字符取出放到末尾……这样能得到\(n\)个字符串。将......
  • P4053 [JSOI2007] 建筑抢修
    [JSOI2007]建筑抢修题目描述小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T部落消灭了所有Z部落的入侵者。但是T部落的基地里已经有......
  • [JSOI2007]祖玛
    做题时间:2022.9.28\(【题目描述】\)给定一排\(N\)个整数,可以向之间插入任意一个整数,得到相邻的多于2个相同的整数就可以把他们消除掉,其余整数按顺序合并起来,也可以继续......
  • [JSOI2007]文本生成器【AC自动机+DP】
    下定决心想要将这份爱意传达给你,与你在一起的每一刻总是那么值得珍藏,你的存在左右着我的思绪,实在是不想错过这样的美好,真的不和我在一起吗?我的学术生涯,虽然有点奇妙,......
  • [JSOI2007] 字串加密
    题链:luoguJS同学?Description让JS同学对环形字符串进行重组加密。加密规则是:列出\(n\)个字符串并字典序升序,一次取末尾字符作为加密后的长度为\(n\)的密码串。......