目录
题面
链接
题意
给一个数组\(a\),然后让你给这个数组加上一个排列,求出现最多的次数
题解
赛时没过不应该。
最开始很容易想到要去重,因为重复的元素对于答案是没有贡献的。
去重后排序。,然后维护一个极差小于n-1的区间,,区间长度就是可能的答案。
可以用双指针去实现。
代码
#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
const int N=1e5+10;
void solve()
{
int n;cin>>n;
vector<int>a(n+1);
rep(i,1,n){
cin>>a[i];
}
sort(a.begin()+1,a.end());
set<int>s;
deque<int>q;
int ans=0;
rep(i,1,n){
while(q.size()&&a[i]-a[q.front()]>=n){
s.erase(a[q.front()]);
q.pop_front();
}
q.pb(i);
s.insert(a[i]);
int t=s.size();
ans=max(ans,t);
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
int _;
cin>>_;
while(_--)
solve();
return 0;
}
标签:int,rep,Codeforces,long,Equalize,front,Div,define
From: https://www.cnblogs.com/cxy8/p/18014121