目录
Q: The Kth Time Query
题意:
思路:
题解:
Q: The Kth Time Query 题意:给定一个长度为n的正整形数组,之后给出Q次询问,对于每次询问给出x,k,表示输出x第k次出现的位置,若x,k不存在,就输出-1。
思路:定义一个结构体,包括int x,int k,int l,记录x第k次出现在l处;
用map记录当前x是第几次出现,以便统计结构体中得k;
重载sort函数,对结构体数组排序,二分法查找(x,k,两个比较量);
题解:#includeusing namespace std; struct s { int x; int k; int l; }p[10000010]; bool cmp(s x,s y) { if(x.x==y.x) return x.k mp; int main() { int n,q,x,k; cin>>n>>q; for(int i=1;i<=n;i++) { cin>>x; mp[x]++; p[i].x=x; p[i].k=mp[x]; p[i].l=i; } sort(p+1,p+n+1,cmp); while(q--) { cin>>x>>k; if(mp[x] == 0) { cout<<-1<<"n"; continue; } else if(mp[x] < k) { cout<<-1<<"n"; continue; } int l=1,r=n,mid,pt=0; while(l<=r) { mid=(l+r)/2; if(p[mid].x==x&&p[mid].k==k) {cout<