Build-In Structures

$175$. Distinct Numbers

$set$。

因为$set$不是多重集合，所以将$x$存到$set$中直接输出大小即可。

#include<bits/stdc++.h>
using namespace std;
set<int> a;
int main(){
	freopen("dis.in","r",stdin);
	freopen("dis.out","w",stdout); 
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		a.insert(x);
	}
	cout<<a.size();
	return 0;
}

$176$. Apartments

双指针。

其实我感觉第二道题根本不要用数据结构，数组即可

思路其实和判断子序列这题差不多，我们先排序，然后就用遍历，若条件满足，$i$，$j$都++，否则就让两个数中小的++。

#include<bits/stdc++.h>
using namespace std;
int a[200010],b[200010];
int main(){
	freopen("apartments.in","r",stdin);
	freopen("apartments.out","w",stdout); 
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	int ans=0;
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	for(int i=1,j=1;i<=n&&j<=m;){
		if(abs(a[i]-b[j])<=k){
			ans++;
			i++,j++;
		}
		else if(a[i]>=b[j]) j++;
		else i++;
	}
	cout<<ans;
	return 0;
}

$177$. Concert Tickets

二分。

一眼就可以看出来是二分，所以直接用$set$里的$lower$_$bound$即可，然后将这个数从$set$里删除。

#include<bits/stdc++.h>
using namespace std;
set<pair<int,int>> a;
int main(){
	freopen("tickets.in","r",stdin);
	freopen("tickets.out","w",stdout); 
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
	    a.insert({x, i});
	}
	for(int i=0;i<m;i++){
		int x;
        cin>>x;
        auto it=a.lower_bound({x+1,0});
        if(it!=a.begin()){
            it--;
            cout<<(*it).first<<endl;
            a.erase(it);
        }
        else cout<<-1<<endl;
    }
	return 0;
}

$178$. Traffic Lights

$set$与$multiset$。

我们读完题目后可以发现：其实每一次安装红绿灯，序列都会分成两部分（设这次安装的位置是$x$），[$0$，$x$]，[$x$，$n$]。

那么我们就可以在每次的基础上改动，得到最大值，那么怎么得到最大值呢？用$multiset$即可，每次输出最后一个即可。

#include<bits/stdc++.h>
using namespace std;
set<int> a;
multiset<int> b;
int main(){
	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout); 
	int x,n;
	cin>>x>>n;
	a.insert(0);
	a.insert(x);
	b.insert(x);
	while(n--){
		int i;
		cin>>i;
		auto c=a.upper_bound(i);
		auto d=c;
		d--;
		b.erase(b.find(*c-*d));
        b.insert(i-*d); 
        b.insert(*c-i);
        a.insert(i);
        cout<<*--b.end()<<" ";
	}
	return 0;
}

$174$. Room Allocation

$priority$_$queue$（优先队列中的小根堆）。

这道题目首先要求出第一个答案，那怎么求出来呢？很简单！若现在要进去，计数器++，反之则计数器--。

那第二个答案怎么求出来呢？实际上第二个问题是让我们维护一个区间的最小值，那就要用$priority$_$queue$（优先队列中的小根堆）。

我们可以这么分配房间：

• 若有人退房，则安排最小的房号。
• 不然就安排新的房号。

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> fj;
struct P{
	int day,dh,idx;
};
P a[400010];
bool cmp(P a,P b){
	if(a.day==b.day) return a.dh<b.dh;
	return a.day<b.day; 
}
int main(){
	freopen("room.in","r",stdin);
	freopen("room.out","w",stdout); 
	int n;
	cin>>n;
	for(int i=1;i<=2*n;i++){
		cin>>a[i].day;
		if(i%2==1){
			a[i].dh=1;
			a[i].idx=(i+1)/2;
		}
		else{
			a[i].dh=2;
			a[i].idx=i/2;
		}
	}
	sort(a+1,a+1+n*2,cmp);
	int cnt=0,ans=0;
	for(int i=1;i<=2*n;i++){
		if(a[i].dh==2) cnt--;
		else cnt++;
		ans=max(cnt,ans);
	}
	cout<<ans<<endl;
	int sum=1;
	vector<int> da(n);
	for(int i=1;i<=2*n;i++){
		int r;
		if(a[i].dh==2) fj.push(da[a[i].idx]);
		else{
			if(!fj.size()) r=sum++;
			else{
				r=fj.top();
				fj.pop();
			}
			da[a[i].idx]=r;
		} 
	}
    for(int i=1;i<=da.size();i++) cout<<da[i]<<" "; 
	return 0;
}