题目描述
Farmer John's N cows (\(1 \leq N \leq 50,000\)) are standing in a line, each described by an integer breed ID.
Cows of the same breed are at risk for getting into an argument with each-other if they are standing too close. Specifically, two cows of the same breed are said to be "crowded" if their positions within the line differ by no more than K (\(1 \leq K < N\)).
Please compute the maximum breed ID of a pair of crowded cows.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
vector<int> ve[maxn];
int main() {
//freopen("input.txt","r",stdin);
int n, k; cin >> n >> k;
for (int i = 1; i <= n; ++i) {
int id; cin >> id;
ve[id].push_back(i);
}
int ans = -1;
for (int i = 0; i <= 1000000; ++i) {
if (ve[i].size() == 0 || ve[i].size() == 1) continue;
int pos1 = ve[i][0];
for (int j = 1; j < ve[i].size(); ++j) {
int pos2 = ve[i][j];
if (pos2-pos1 <= k) {
ans = i;
break;
}
pos1 = pos2;
}
}
cout << ans << endl;
return 0;
}
原文链接: https://www.cnblogs.com/wstong/p/13044023.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/352873
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!