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)


相关推荐

  • RPC接口实现_一个接口多个实现

    RPC接口实现_一个接口多个实现1.RPC作用以目前的认识,RPC的作用:多个工程之间数据传输。2.逐步完成RPC接口实现第一步:编写thrift文件,语法格式和java不同。在布局分层里安排在了client层

    2022年10月13日
  • javaScript的基本语法结构「建议收藏」

    javaScript的基本语法结构「建议收藏」javaScript的基本语法结构一、javascript程序带的文本二、javascript中的注释三、字面量四、标识符和保留字标识符保留字五:可选的分号一、javascript程序带的文本vascript区分大小写。这就意味着他的关键字,变量,函数名和其他标识符必须始终保持一致的大小写格式二、javascript中的注释//这是单行注释/*这也是注释*///而这是另一个注释/**这是多行注释*每行开头的*字符不是必要的,只是为了美观*/三、字面量字面量(litera

  • 如何在Linux系统上刷抖音

    如何在Linux系统上刷抖音如何在linux系统上刷抖音

  • 中国历年人口出生数1983至2020岁_中国历年出生人口数据

    中国历年人口出生数1983至2020岁_中国历年出生人口数据1983年:2052万1984年:2050万1985年:2196万1986年:2374万1987年:2508万1988年:2445万1989年:2396万1990年:2374万1991年:2250万1992年:2113万1993年:2120万1994年:2098万1995年:2052万1996年:2057万1997年:2028万1998年:1934万1999年:1827万2000年:1765万2001年:1696万2002年:1641万2003年:1594万200.

  • SpringBootTest—–踩坑错误

    SpringBootTest—–踩坑错误Springboot降低了我们对spring开发的难度采用了大量在的自动配置,我们只需要进行简单的基本配置,就能快速开发一个spring应用。同样spring对于单元测试也有场景启动器—-spring-boot-starter-test,可以让我们在,spring环境下进行测试。昨天测试的时候,容器都无法启动,检查之后发现了原因,也是因为自己粗心大意。@RunWith(value…

  • struts中的action_type object has no attribute

    struts中的action_type object has no attribute在Strust2中,有一个内置对象叫ActionContext,通过该对象可以获得之前Servlet中的对象,比如:requst对象,response对象…那么为什么可以通过ActionContext获得那些对象呢?那是因为在ActionContext内容引用了那些对象,也就是在ActionContext内部记录了那些对象的地址,看下图上图就是简单理解为什么通过Action

发表回复

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

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