题解思路与方法

问题重述

收容所中有 $n$ 只宠物，第 $i$ 只宠物有领养编号 $x_i$（越小优先级越高），两种毛色 $a_i$ 和 $b_i$。有 $m$ 位领养人，依次到来，每位有偏好毛色 $c_j$，只会领养至少一种毛色符合偏好的宠物，并在剩余符合条件的宠物中选领养编号最小的那只。若无心仪宠物，则放弃（输出 $-1$）。

关键思路

1. 按颜色分堆（最小堆） 因为每位领养人只关心某一种颜色，我们可以为三种颜色各维护一个最小堆（min-heap），堆中存储 (领养编号, 宠物下标)。

2. 去重与懒删除 一只宠物可能出现在两个堆（若 $a_i\neq b_i$），且每次领养时要确保没被重复领养。维护一个布尔数组 used[i] 标记宠物是否已被领养。

3. 模拟领养过程

   • 初始化时，将每个宠物根据其两种毛色分别推入对应颜色的堆（若两色相同，只推一次）。
   • 对于每位领养人偏好颜色 $c$，在对应堆中不断弹出堆顶元素，若对应宠物已被领养则丢弃，直到找到未领养的或堆空。
   • 若找到，则标记 used[idx]=true，输出该宠物的编号；否则输出 -1。

相关算法

• 堆 / 优先队列（Priority Queue）：支持 $O(\log n)$ 时间的插入和弹出最小元素操作。
• 懒删除技术：删除操作在访问时才真正执行，从而避免在堆中进行非根节点的直接删除。

复杂度分析

• 建堆：每只宠物最多插入两次，共 $O(n\log n)$。
• 模拟领养：每次领养最多弹出若干“已失效”节点，但每个节点最多被弹出一次，所有弹出共 $O((n+m)\log n)$。
• 总复杂度：$O\bigl((n+m)\log n\bigr)$，满足 $n\le3\times10^4,\ m\le10^5$ 的要求。

代码实现

Python

import sys
import heapq

def solve():
    input=sys.stdin.readline
    n=int(input())
    xs=list(map(int, input().split()))
    a=list(map(int, input().split()))
    b=list(map(int, input().split()))
    m=int(input())
    c=list(map(int, input().split()))
    
    # 三个颜色的最小堆
    heaps=[[] for _ in range(4)]
    for i in range(n):
        # 推入颜色
        heapq.heappush(heaps[a[i]], (xs[i], i))
        heapq.heappush(heaps[b[i]], (xs[i], i))
    
    used=[False]*n  # 宠物是否被领养
    res=[]
    for col in c:
        h=heaps[col]
        # 弹出已领养的，或直到堆空
        while h and used[h[0][1]]:
            heapq.heappop(h)
        if not h:
            res.append(-1)
        else:
            x,i=h[0]
            used[i]=True
            res.append(x)
    print(' '.join(map(str, res)))

if __name__=="__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(in.readLine());
        StringTokenizer st=new StringTokenizer(in.readLine());
        int[] x=new int[n];
        for(int i=0;i<n;i++) x[i]=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(in.readLine());
        int[] a=new int[n];
        for(int i=0;i<n;i++) a[i]=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(in.readLine());
        int[] b=new int[n];
        for(int i=0;i<n;i++) b[i]=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(in.readLine());
        st=new StringTokenizer(in.readLine());
        int[] c=new int[m];
        for(int i=0;i<m;i++) c[i]=Integer.parseInt(st.nextToken());
        
        // 建立三个优先队列
        PriorityQueue<int[]>[] qs = new PriorityQueue[4];
        for(int i=1;i<=3;i++){
            qs[i] = new PriorityQueue<>(Comparator.comparingInt(o->o[0]));
        }
        for(int i=0;i<n;i++){
            qs[a[i]].offer(new int[]{x[i], i});
            qs[b[i]].offer(new int[]{x[i], i});
        }
        
        boolean[] used=new boolean[n];
        StringBuilder ans=new StringBuilder();
        for(int col:c){
            PriorityQueue<int[]> q=qs[col];
            while(!q.isEmpty() && used[q.peek()[1]]){
                q.poll();
            }
            if(q.isEmpty()){
                ans.append(-1).append(' ');
            } else {
                int[] top=q.poll();
                used[top[1]] = true;
                ans.append(top[0]).append(' ');
            }
        }
        System.out.println(ans.toString().trim());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    cin>>n;
    vector<int> x(n), a(n), b(n);
    for(int i=0;i<n;i++) cin>>x[i];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    int m; 
    cin>>m;
    vector<int> c(m);
    for(int i=0;i<m;i++) cin>>c[i];

    // 三个最小堆，存 (领养编号, 下标)
    vector<priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>> pq(4);
    for(int i=0;i<n;i++){
        pq[a[i]].push({x[i], i});
        pq[b[i]].push({x[i], i});
    }

    vector<bool> used(n,false);
    for(int col:c){
        auto& h = pq[col];
        while(!h.empty() && used[h.top().second]){
            h.pop();
        }
        if(h.empty()){
            cout<<-1<<' ';
        } else {
            auto t=h.top(); h.pop();
            used[t.second]=true;
            cout<<t.first<<' ';
        }
    }
    return 0;
}

题目内容

某宠物收容所有 $n$ 只宠物，这些宠物每一只都有两种毛色，第 $i$ 只宠物的第一种毛色为 $ai$，第二种毛色为 $bi$ 。另外根据收容时长，收容所赋予了每个宠物唯一的“领养编号” $xi$ ，可理解为领养优先级，编号越小优先级越高。 近期收容所开放了宠物领养活动。共有 $m$ 个领养人依次来到收容所，每个领养人都有一个偏好的毛色，记为 $ci$ 。领养人只会领养第一种毛色或第二种毛色中至少一种是他们偏好毛色的宠物。如果收容所剩余的宠物中有当前领养人偏好的宠物，则他会选择符合要求的宠物中领养编号最小的那一只宠物。如果没有心仪的宠物(或已经没有剩余的宠物)则会放弃领养。只有当前一位领养人领养结束后(或放弃领养)，下一位领养人才会来到收容所进行领养。领养活动结束后，收容所想要了解每个领养人领养宠物的情况，请你帮助他们进行统计。

输入描述

第一行一个正整数 $n$ ，表示最开始收容所的宠物数量。

第二行 $n$ 个正整数，第 $i$ 个数 $xi$ 表示第 $i$ 只宠物的领养编号。

第三行 $n$ 个正整数，第 $i$ 个数 $ai$ 表示第 $i$ 只宠物的第一种毛色。

第四行 $n$ 个正整数，第 $i$ 个数 $bi$ 表示第 $i$ 只宠物的第二种毛色。

第五行一个正整数 $m$ ，表示领养人数量。

第六行 $m$ 个正整数，第 $i$ 个数 $ci$ 表示第i位领养人偏好的毛色。

$1≤xi≤10^9$，$1≤ai,bi,ci≤3$，$1≤n≤30000$，$1≤m≤100000$

输出描述

输出一行共 $m$ 个数，第 $i$ 个数表示第 $i$ 位领养人领养宠物的“领养编号"，如果第 $i$ 位领养人没有领养宠物，则输出 $-1$ 。

样例1

输入

4
25 10 5 40
1 2 3 1
3 1 2 2
5
2 1 3 2 1

输出

5 10 25 40 -1

说明

第一位领养人偏好毛色 $2$ ：有多只符合毛色的，选择领养编号最小为 $5$ 的(第 $3$ 只)。剩余宠物 $1、2、4$ 。

第二位领养人偏好毛色 $1$ ：有多只符合毛色的，选择领养编号最小为 $10$ 的(第 $2$ 只)。剩余宠物 $1、4$ 。

第三位领养人偏好毛色 $3$ ：符合条件的宠物只有第 $1$ 只，领养编号 $25$ 。剩余宠物 $4$ 。

第四位领养人偏好毛色 $2$ ：符合条件的宠物只有第 $4$ 只，领养编号 $40$ 。无剩余宠物。

第五位领养人偏好毛色 $1$ ：无剩余宠物，输出 $-1$ 。