首页 > 其他分享 >P2949 [USACO09OPEN] Work Scheduling G

P2949 [USACO09OPEN] Work Scheduling G

时间:2025-01-09 23:24:17浏览次数:1  
标签:std USACO09OPEN int Work 工作 日期 Scheduling 我们 截止

题意:有n个工作可以做,它们有截止日期和价值,每个工作需要一天完成,你从0时刻开始做,求最大收益。

我们肯定希望尽早完成某个任务,那么我们一天也不能闲,一天做一个任务。
于是我们将工作按截止日期从小到大排序,如果第i个工作的截止日期小于等于我们做的任务数(任务数就等于我们做到的天数,因为我们一天做一个),那么就拿它和我们做过的工作中最小的价值比较,如果它更大那就更换,因为这样收益更大。这相当于将我们完成前面工作的那天来做第i个工作,因为我们存的都是前面的工作,截止日期比当前这个小,那么能做之前的也能做这个。
对于截止日期大于我们完成的任务数的,直接加进来就行。
可以用优先队列维护。

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

	std::sort(a.begin(), a.end());

	std::priority_queue<int, std::vector<int>, std::greater<int> > heap;

	i64 ans = 0;
	for (int i = 0; i < n; ++ i) {
		if (a[i].first <= heap.size()) {
			if (heap.top() < a[i].second) {
				ans = ans - heap.top() + a[i].second;
				heap.pop();
				heap.push(a[i].second);
			} 
		} else {
			heap.push(a[i].second);
			ans += a[i].second;
		}
	}

	std::cout << ans << "\n";
}

标签:std,USACO09OPEN,int,Work,工作,日期,Scheduling,我们,截止
From: https://www.cnblogs.com/maburb/p/18663068

相关文章

  • OSPF - 2、3类LSA(Network-LSA、NetWork-Sunmmary-LSA)
    前篇博客有对常用LSA的总结2类LSA(Network-LSA)DR产生泛洪范围为本区域作用: 描述MA网络拓扑信息和网络信息,拓扑信息主要描述当前MA网络中伪节点连接着哪几台路由。网络信息描述当前网络的掩码和DR接口IP地址。影响邻居建立中说到MA网络掩码需要一致,就是因为这里2类LS......
  • 有限元分析学习——Anasys Workbanch第一阶段笔记(8)水杯案例的对称与轴对称处理
    目录1序言2对称处理2.1模型处理 2.2网格划分、约束载荷及接触设置2.3计算结果3轴对称处理3.1对称与轴对称概念3.2轴对称问题的应用 3.2.1 创建分析案例3.2.2导入并处理模型3.2.3网格划分、约束载荷及接触设置3.2.4后处理计算结果1序言本章主要介......
  • Unity QFrameWork--IOC
    IOCContainerusingSystem;usingSystem.Collections.Generic;namespaceQFramework{publicclassIOCContainer{///<summary>///存储实例///</summary>publicDictionary<Type,object>mInstances=ne......
  • Unity QFrameWork--Singleton
    SingletonusingSystem;usingSystem.Reflection;namespaceQFramework{publicclassSingleton<T>whereT:Singleton<T>{privatestaticTmInstance;publicstaticTInstance{get{......
  • Recursive Decomposition of Logical Thoughts: Framework for Superior Reasoning an
    题目逻辑思维的递归分解:大型语言模型中高级推理和知识传播的框架论文地址:https://arxiv.org/abs/2501.02026摘要    增强大型语言模型的推理能力仍然是人工智能领域的一大挑战。我们引入了RDoLT(逻辑思维递归分解)提示,这是一个显著提高LLM推理性能的新颖框架。RD......
  • vue3项目yarn install遇到的info There appears to be trouble with your network con
    新接手的vue3项目在安装依赖的时候经常下载失败,报错Couldn'tfindpackage...onthe"npm"registry或者errorError:readECONNRESET1.可以改变当前的源查看当前使用的源yarnconfiggetregistry改变源yarnconfigsetregistryhttps://registry.npmmirror.com(推荐......
  • nifi下载Win版本安装成功运行_network
    一、Apachenifi相关网址https://nifi.apache.org/ 官网https://nifi.apache.org/docs.html 文档https://nifi.apache.org/download.html 下载页##二、Apachenifi本地安装进入https://nifi.apache.org/download.html解压到本地bin目录下有启动和......
  • python 代码实现了一个条件生成对抗网络(Conditional Generative Adversarial Network,C
    importtensorflowastfimportnumpyasnpimportpandasaspdimportosimportmatplotlib.pyplotaspltfromsklearn.model_selectionimporttrain_test_splitfromtensorflow.keras.layersimportAdd,BatchNormalizationos.environ["KMP_DUPLICATE_LIB_O......
  • Ultra-Low Precision 4-bit Training of Deep Neural Networks
    目录概主要内容Radix-4FP4formatGradScaleTwo-PhaseRounding(TPR)SunX.,WangN.,ChenC.,NiJ.,AgrawalA.,CuiX.,VenkataramaniS.andMaghraouiK.E.andSrinivasanV.Ultra-lowprecision4-bittrainingofdeepneuralnetworks.NeurIPS,2020.概本文......
  • 在 .NET Framework 中,C#代码防止按钮重复点击的后端处理
    ai生成:在.NETFramework中,防止按钮重复点击的后端处理通常涉及到Web应用程序(如ASP.NETWebForms或ASP.NETMVC)。以下是一些常见的后端处理方法和示例代码:ASP.NETWebForms在WebForms中,你可以使用ViewState或Session来防止按钮重复点击。以下是一个使用ViewSta......