题目描述：
农夫约翰的 $ N $ 头奶牛排成一排，每头奶牛都用其品种 ID 进行描述。
如果两头相同品种的牛靠得太近，它们就会吵架。
具体的说，如果同一品种的两头奶牛在队列中的位置相差不超过 $ K $ ，我们就称这是一对拥挤的牛。
请计算品种 ID 最大的拥挤奶牛对的品种 ID。
输入格式
第一行包含两个整数 $ N $ 和 $ K $ 。
接下来 $ N $ 行，每行包含一个整数表示队列中一头奶牛的品种 ID。
输出格式
输出品种 ID 最大的拥挤奶牛对的品种 ID。
如果不存在拥挤奶牛队，则输出 $ −1 $ 。
数据范围
品种 ID 范围 $ [0,10^6] $ 。
输入样例：
输出样例：
题解：
题意是让求最大的 ID。直接使用长度为 $ K + 1 $ 的滑动窗口去滑动，就能得到答案。注意和单调队列的区别，单调队列可能会一直出队。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int q[maxn];
int hh, tt;
int times[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
k++;
hh = 0, tt = 0;
int ans = -1;
for (int i = 1, id; i <= n; i++)
{
cin >> id;
q[tt++] = id;
times[id]++;
if (tt - hh > k)
{
times[q[hh++]]--;
}
if (times[id] >= 2)
{
ans = max(ans, id);
}
}
cout << ans << endl;
return 0;
}
|