题目链接:https://codeforces.com/contest/1676/problem/F
大意就是输入一个k和一堆数
找到一组连续的且其中每个数出现的次数大于等于k次 即 [L,R] 中 每个元素出现的次数至少k次,输出最多的那一组的左端点元素和右端点元素
如果有多组输出任意 ,输出 L和R ,如果没有符合条件的一组,就输出-1
根据输入数据的特性,我们可以考虑使用map ,frist为输入的数,second为输入数的次数
然后使用迭代器进行查找。找到最大的数量和对应的R ,通过R - cnt +1 推算出 L
代码:
#include<bits/stdc++.h> using namespace std; map<int,int>mp; int main() { int t,n,k; cin>>t; while(t--) { cin>>n>>k; for(int i=1;i<=n;i++) { int x; cin>>x; mp[x]++; } int cnt = 0,now = 0,maxt = 0, next = 0; for(auto it=mp.begin(); it!=mp.end(); it++) { if(it->first!=now) { cnt = 0; now = it->first; } if(it->second < k) cnt =0; else { cnt++; if(cnt>maxt) { maxt = cnt ; next = it->first; } } now ++; } if(maxt == 0) cout << "-1" << endl; else cout << next - maxt + 1 << " " << next << endl;//末尾减去数量+1就等于了首位 mp.clear(); } return 0; }