Concert Tickets 二分+并查集

题目描述

There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another.
Each customer announces the maximum price they are willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

输入

The first input line contains integers n and m（1≤ n, m≤ 2*105）: the number of tickets and the number of customers.
The next line contains n integers h1,h2,...,hn（1≤ hi≤ 109）: the price of each ticket.
The last line contains m integers t1,t2,...,tm（1≤ ti≤ 109）: the maximum price for each customer in the order they arrive.

输出

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.
If a customer cannot get any ticket, print -1.

样例输入 Copy

5 3
5 3 7 8 5
4 8 3

样例输出 Copy

3
8
-1

二分查找，分配门票（每个人越贵越好）

用并查集查询已经被购买的情况（一直查询更小的票价，售空为止）

find需要特判-1的情况，不然会运行错误

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,t[200009],h[200009],c[200009];
int find(int x){if(x==-1)return -1;if(c[x]!=x)c[x]=find(c[x]);return c[x];
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;++i)scanf("%d",&h[i]);for(int i=0;i<n;++i)c[i]=i;for(int i=0;i<m;++i)scanf("%d",&t[i]);sort(h,h+n);for(int i=0;i<m;++i){int l=0,r=n-1,mid,p=-1;while(l<=r){mid=(l+r)>>1;if(h[mid]>t[i]){r=mid-1;}else{l=mid+1;p=mid;}}if(p==-1){cout<<-1<<'\n';continue;}int ans=find(c[p]);if(ans==-1){cout<<ans<<'\n';}else{cout<<h[ans]<<'\n';c[ans]=(ans==0)?-1:find(ans-1);}}return 0;
}