HDU4907小技巧

HDU4907小技巧

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

原题http://acm.hdu.edu.cn/showproblem.php?pid=4907

Task schedule

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 692    Accepted Submission(s): 334

Problem Description
有一台机器,而且给你这台机器的工作表,工作表上有n个任务,机器在ti时间运行第i个任务,1秒就可以完毕1个任务。

有m个询问,每一个询问有一个数字q,表示假设在q时间有一个工作表之外的任务请求,请计算何时这个任务才干被运行。

机器总是依照工作表运行,当机器空暇时马上运行工作表之外的任务请求。

 

Input
输入的第一行包括一个整数T, 表示一共同拥有T组測试数据。

对于每组測试数据:

第一行是两个数字n, m,表示工作表里面有n个任务, 有m个询问;

第二行是n个不同的数字t1, t2, t3….tn,表示机器在ti时间运行第i个任务。

接下来m行,每一行有一个数字q,表示在q时间有一个工作表之外的任务请求。

特别提醒:m个询问之间是无关的。

[Technical Specification]

1. T <= 50

2. 1 <= n, m <= 10^5

3. 1 <= ti <= 2*10^5, 1 <= i <= n

4. 1 <= q <= 2*10^5

 

Output
对于每个询问,请计算并输出该任务何时才干被运行,每个询问输出一行。

 

Sample Input
   
   
1 5 5 1 2 3 5 6 1 2 3 4 5

 

Sample Output
   
   
4 4 4 4 7

//本题要是直接做会超时,所以採用预处理的方法。听说二分也能够,只是没有试过,感觉预处理已经挺快的了
//思路,开个数组,代表在i秒进行额外工作的时间。非常明显,在预处理的时候要从后往前找
//假设该时间该机器本身不须要工作,那么就吧时间不断的缩小
include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <limits.h>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define N 100000 + 10
#define M 200000 + 10
int vis[M];
int take[M];

int main(){
	int T,n,m;

	while(~scanf("%d",&T)){
		while(T--){
			memset(vis,0,sizeof(vis));
			memset(take,0,sizeof(take));
			scanf("%d%d",&n,&m);
			int i,num;
			for(i=1;i<=n;i++){
				scanf("%d",&num);
				vis[num] = 1;
			}
			int mark;
			for(i=200000;i>=1;i--){
				take[i] = i;
				if(vis[i] == 0){
					mark = i;
				}
				else{
					take[i] = mark;
				}
			}
			int t;
			for(i=1;i<=m;i++){
				scanf("%d",&t);
				printf("%d\n",take[t]);
			}
		}
	}

	return 0;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118733.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Flowable工作流入门

    Flowable工作流入门Flowable工作流入门本文链接:https://blog.csdn.net/qq_37059838/article/details/83576097原作者:吕小小布下载地址:Flowable下载使用springbootflowble生成所需表<dependency><groupId>org.flowable</gro…

  • elasticsearch 索引重命名[通俗易懂]

    elasticsearch 索引重命名[通俗易懂]直接复制索引到新的索引名称POSTlocalhost:9200/_reindex{"source":{"index":"indexName"},"dest":{"index":"newIndexName"}}查询复制索引到新的索引名称POSTlocalhost:9200/_reindex{"source&

  • Fiddler工具之Filters[通俗易懂]

    Fiddler工具之Filters[通俗易懂]Fiddler工具之FiltersFiddler是一个强大的抓包工具,可以抓取Http/Https协议的数据包,也可以实现截包、过滤包,修改包等等,今天我们一起学习一下Fildder中Filters功能的滤过包和截包;1、首先打开Fiddler主界面,查看右侧功能区选择Filfters标签,勾选UseFilters复选框;(图1)Hosts配置2、Fiddler默认是会拦截所有的…

  • java arraylist遍历_遍历ArrayList的4种方法

    java arraylist遍历_遍历ArrayList的4种方法以下4种方法有什么不同,个人感觉好象没什么不同..除了用跌代器看上去比较帅以外….packagecom.test;importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;publicclassArrayListDemo{publicstaticvoidmain(Stringargs[]…

  • 俄罗斯方块(C语言实现)

    俄罗斯方块(C语言实现)文章目录游戏说明游戏效果展示游戏代码游戏代码详解游戏框架构建隐藏光标光标跳转初始化界面初始化方块信息颜色设置画出方块空格覆盖合法性判断游戏主体逻辑函数判断得分与结束主函数游戏说明俄罗斯方块相信大家都知道,这里就不再介绍什么游戏背景了,我这里对本代码实现的俄罗斯方块作一些说明:按方向键的左右键可实现方块的左右移动。按方向键的下键可实现方块的加速下落。按空格键可实现方块的顺时针旋转。按Esc键可退出游戏。按S键可暂停游戏,暂停游戏后按任意键继续游戏。按R键可重新开始游戏。除此之外,本游戏还

  • javaweb-svn-1-60

    javaweb-svn-1-60

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号