【bzoj2793】[Poi2012]Vouchers 暴力

题目描述

考虑正整数集合，现在有n组人依次来取数，假设第i组来了x人，他们每个取的数一定是x的倍数，并且是还剩下的最小的x个。
正整数中有m个数被标成了幸运数，问有哪些人取到了幸运数。

输入

第一行一个正整数m (m<=1,000,000)，下面m行每行一个正整数x (x<=1,000,000)，表示x是一个幸运数。
接下来一行一个正整数n (n<=1,000,000)，下面n行每行一个正整数x (x<=1,000,000)，表示这一组来了x个人。

输出

第一行输出一个非负整数k，表示k个人取到了幸运数，下面k行依次表示取到幸运数的人的编号，人按照来的顺序从1开始编号。

样例输入

4
1
6
8
16
3
4
2
4

样例输出

3
2
4
6

题解

暴力

考虑：取的数超过了最大的幸运数便没有了意义，因此当某次取的数超过最大幸运数时直接停止取数即可。

于是可以对于每个x，维护pos[x]，表示x人组下一次应该取的位置。这些位置以前的一定是取过的，因此下一次直接从该位置向后判断即可。

然后只需要维护一个数是否使用过即可。

时间复杂度为某调和级数的$O(n\ln n)$

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 1000010

using namespace std;

int tag[N] , vis[N] , pos[N] , tot;

long long sta[N];

int main()

{

	int n = 0 , m , k , i , x;

	long long now = 0;

	scanf("%d" , &m);

	for(i = 1 ; i <= m ; i ++ ) scanf("%d" , &x) , tag[x] = 1 , n = max(n , x);

	for(i = 1 ; i <= n ; i ++ ) pos[i] = i;

	scanf("%d" , &k);

	while(k -- )

	{

		scanf("%d" , &x);

		for(i = 1 ; i <= x ; i ++ )

		{

			while(pos[x] <= n && vis[pos[x]]) pos[x] += x;

			if(pos[x] > n) break;

			if(tag[pos[x]]) sta[++tot] = now + i;

			vis[pos[x]] = 1;

		}

		now += x;

	}

	printf("%d\n" , tot);

	for(i = 1 ; i <= tot ; i ++ ) printf("%lld\n" , sta[i]);

	return 0;

}

巴特西

【bzoj2793】[Poi2012]Vouchers 暴力

最新文章

热门文章