C - Except and Min

题目描述:

现有N个球，每个球上有一个对应的值，有Q个查询，给出要删除的球的序号，输出剩下的球中值最小的那个。

解题思路:

这题Q的范围最大是2e5，而它每次查询删除的球k<=5，所以可以直接对原数组和序号按球上的值升序排序，然后用一个map记录删除球的序号，最坏就是5个球正好是前5个最小的，第六个循环查询到，时间复杂度为O(6Q)

示例代码:

bool cmp(pair<int,int> a,pair<int,int> b)
{
	return a.second < b.second;
}
void solve()
{
    int n,q;
    cin >> n >> q;
    vector<pair<int,int>> a(n);
    for(int i=0;i<n;i++){
    	cin >> a[i].second;
    	a[i].first=i+1;
	}
	sort(a.begin(),a.end(),cmp);
    while(q--){
		int x,w;
		cin >> x;
		map<int,int> mp;
		for(int i=0;i<x;i++){
			cin >> w;
			mp[w]=1;
		}
		for(int i=0;i<n;i++)
			if(!mp[a[i].first]){
				cout << a[i].second << endl;
				break;
			}
	}
    return;
}