浙江财经大学
信息管理与工程学院

HDU 4907 Task schedule

本文由 Ocrosoft 于 2016-08-25 21:20:31 发表

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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

Solition

预处理,看一下代码就会懂的。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX / 2;
const int MAXN = 200000 + 10;
using namespace std;
int a[MAXN];
int ans[MAXN];
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int n, m;
		cin >> n >> m;
		ms(a); ms(ans);
		for (int i = 0; i < n; i++)
		{
			int t;
			scanf("%d", &t);
			a[t] = 1;
		}
		int j = n;
		for (int i = 200001; i >= 0; i--)
		{
			if (!a[i])j = i;
			ans[i] = j;
		}
		while (m--)
		{
			int t;
			scanf("%d", &t);
			printf("%d\n", ans[t]);
		}
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » HDU 4907 Task schedule

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址