Task
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1679 Accepted Submission(s): 428
Problem Description
Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500*xi+2*yi) dollars.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.
Input
The input contains several test cases.
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the maximum time the machine can work.yi is the level of the machine.
The following M lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the time we need to complete the task.yi is the level of the task.
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the maximum time the machine can work.yi is the level of the machine.
The following M lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the time we need to complete the task.yi is the level of the task.
Output
For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.
Sample Input
1 2 100 3 100 2 100 1
Sample Output
1 50004
题意:
给出 N(1 ~ 100000)部机器,M (1 ~ 100000)个任务,每个任务只能由一部机器完成,每个机器只能完成一个任务,当机器的时间和难度值都大于任务的时间和难度值才能去完成任务。后给出 N 部机器的难度值和 M 部机器的时间和难度值。问如何安排能使完成的任务数最多且同样多的情况下获得的钱数最多。每次完成一个任务则获得 500 * 时间 + 2 * 难度值 的钱。
思路:
贪心。时间从大到小排序后,用任务去选择机器,挑出所有时间大于任务时间的机器中难度值大于任务且难度值最小的机器去完成。因为难度值最大才有 100,所以可以用数组统计机器的数量。记得钱数是 long long 的。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MAX = 100005; typedef struct { int time, level; } node; node machine[MAX], task[MAX]; int level[105]; bool cmp (node a, node b) { if (a.time != b.time) return a.time > b.time; return a.level > b.level; } int main() { int n, m; while (~scanf("%d%d", &n, &m)) { for (int i = 0; i < n; ++i) { scanf("%d%d", &machine[i].time, &machine[i].level); } for (int i = 0; i < m; ++i) { scanf("%d%d", &task[i].time, &task[i].level); } sort(machine, machine + n, cmp); sort(task, task + m, cmp); memset(level, 0, sizeof(level)); int ans = 0, mm = 0; ll sum = 0; for (int i = 0; i < m; ++i) { while (mm != n && machine[mm].time >= task[i].time) { ++level[ machine[mm].level ]; ++mm; } for (int k = task[i].level; k <= 100; ++k) { if (level[k] > 0) { --level[k]; ++ans; sum += (ll)(task[i].time * 500 + 2 * task[i].level); break; } } } printf("%d %I64d\n", ans, sum); } return 0; }
相关推荐
Independent Task Scheduling
云计算中融入贪心策略的调度算法研究,周舟,胡志刚,鉴于Min-Min算法优先调度小任务而Max-Min算法优先调度大任务而导致云系统资源不平衡的问题,提出了一种新的算法叫Min-Max. Min-Max算法对时
内容介绍 ...贪心调参方法; 网格调参方法; 贝叶斯调参方法; 相关原理介绍与推荐 线性回归模型:https://zhuanlan.zhihu.com/p/49480391 决策树模型:https://zhuanlan.zhihu.com/p/65304798 GBOT模型
建模与调参 学习目标 掌握机器学习模型的建模与调参过程 ...贪心调参方法; 网格调参方法; 贝叶斯调参方法; 代码示例 import pandas as pd import numpy as np import warnings warnings.filterw
题目描述 123.买卖股票的最佳时机 III 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你...
爬山算法是一种简单的贪心搜索算法,这个算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到找到一个局部最优解。而其有一个主要的缺陷,即该算法会陷入因搜索到局部最优解,而无法搜索到全局最优解的...
本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。...
Task2中的循环神经网络部分,有实现预测歌词的功能。在那个任务中,训练数据的输入输出长度是固定的,而在机器翻译中,输出的长度是不固定的,所以不能直接用RNN来处理这种任务。 Encoder-Decoder框架是常用于机器...
本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。...
本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。...
本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。...
(一)机器翻译及其相关技术 1. 机器翻译(MT):将一段文本从一种语言自动翻译为另一种语言,用神经网络解决这个问题通常称为神经机器翻译(NMT)...Beam Search 一个贪心算法 维特比算法:选择整体分数最高的句子
matlab精度检验代码全球网格导航的Q学习 该项目用于实现世界网格导航的Q学习算法。 Matlab已用于实现。 问题陈述 假设机器人要在10 x 10的网格上移动,开始...编写一个MATLAB(M文件)程序来实现Q学习算法,使用task1
task 0、查漏补缺,将C语言基础语法必须全部学会,如下内容不需要在力扣和牛客网上寻找,请编程实现: (a)欧几里得算法求最大公约数, (b)筛法求素数, (c)康托展开, (d)逆康托展开 (e)同余定理 (f)高...
1149 Dividing up 经典题,可以用1366的方法做,利用问题的特殊性用贪心做出来 1222 Just the Facts 经典题,据说可能有O(logn)的做法,但我没想到:( 1475 Ranklist 没有完美解决,不知道您有没有好方法…… 1572 ...
1149 Dividing up 经典题,可以用1366的方法做,利用问题的特殊性用贪心做出来 1222 Just the Facts 经典题,据说可能有O(logn)的做法,但我没想到:( 1475 Ranklist 没有完美解决,不知道您有没有好方法…… 1572 ...
分治思想 算法洗脑系列(8篇)——第四篇 枚举思想 算法洗脑系列(8篇)——第三篇 贪心思想 算法洗脑系列(8篇)——第二篇 递归思想 算法洗脑系列(8篇)——第一篇 递推思想 天籁数学(3)天籁数学——数列篇(3) ...