Description
给定 (m) 个城市,每年会选择一个城市举办比赛,现在给出前 (n) 年举办比赛的情况。在接下来的年份中,每年的比赛会在举办比赛次数最小的城市举办,如果有多个最小值,则先在编号最小的城市举办。有 (q) 个询问,每个询问给定一个 (k),问第 (k) 年在哪个城市举办比赛。
Solution
考虑离线处理,将询问排序,维护一个集合表示当前轮可以举办的城市的编号集合,每次通过暴力 kth 来找答案,这样需要用平衡树维护,考虑是否有更简单的做法
前 (n) 场比赛每一场都会恰好使得后面的一场比赛被跳过,我们只需要求出被跳过的比赛的时刻即可
先不考虑被跳过的比赛之间的相互作用,设前 (n) 场中的第 (i) 场的举办地点是 (x),前 (i) 场中在 (x) 举办的场数是 (c[x]),则导致的被跳过的比赛的原有时刻为 (mcdot c[x]+x - 1)
由于跳过的比赛之间会相互影响,我们不妨先记为 (a[i]=m cdot c[x] + x),在对所有比赛进行排序后,令 (a[i]=a[i]-i),即得到了每次跳过的时间
最后求解答案时,只需要二分一下,减去 (a[i] le k-n) 的个数即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,m,k,q,c[N],a[N];
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[i]=m*c[x]+x;
c[x]++;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
a[i]-=i;
}
for(int i=1;i<=q;i++)
{
cin>>k;
int ans=lower_bound(a+1,a+n+1,k-n)-a-n-1;
cout<<(ans+k-1+m)%m+1<<endl;
}
}