题解：CF39F Pacifist frogs

题目分析

这道题肯定可以用桶做，但

1 \le n \le 10^9

，存不下，得再换一种方法。

观察题目，可以发现每只青蛙的跳跃的长度是固定的。所以，我们只需要判断每只蚊子所在的位置是不是青蛙的跳跃的长度，如果是，就加到这只青蛙吃蚊子的数量中。最后再算一下最小值和最小值的个数。时间复杂度

O(mk)

。

代码

CPP

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
inline ll read()
{
	ll res = 0, f = 1;
	char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e2 + 5;
int n = read(), m = read(), k = read();
int d[N], p[N], ans[N], minn = INT_MAX, cnt;
int main()
{
	for (int i = 1; i <= m; i++) d[i] = read();
	for (int i = 1; i <= k; i++) p[i] = read();
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= k; j++)
			if (p[j] % d[i] == 0) ans[i]++; //是否是跳跃长度的倍数 
		if (ans[i] == minn) cnt++; // 统计最小值的个数 
		else if (ans[i] < minn) minn = ans[i], cnt = 1; // 更新最小值 
	}
	writech(cnt, '\n');
	for (int i = 1; i <= m; i++)
		if (ans[i] == minn) writech(i, ' ');
	return 0;
}

题解：CF39F Pacifist frogs

文章操作

题目分析

代码

相关推荐

评论

题解：CF39F Pacifist frogs