Problem
T1
感觉是最难的。
考虑贪心。
首先对牛的按左端点进行排序,然后对于每只鸡去考虑匹配哪头牛。
具体地,开一个小根堆,然后对于每只鸡 \(t_i\),将 \(a_i \le t_i\) 的牛放入堆中,此时堆中存放的是候选的牛。
然后对于堆中的牛,将 \(b_i<t_i\) 的牛弹出。
此时堆中的牛均是合法的,累加堆的大小即可。
#include<bits/stdc++.h>
using namespace std;
int c,n,ans;
int t[20031];
struct node{
int x,y;
friend bool operator < (node a,node b){
return a.y>b.y;
}
}a[20031];
priority_queue<node> pq;
bool cmp(node a,node b){
return a.x<b.x;
}
int main(){
cin>>c>>n;
for(int i=1;i<=c;i++) cin>>t[i];
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(t+1,t+c+1),sort(a+1,a+n+1,cmp);
for(int i=1,now=1;i<=c;i++){
while(now<=n&&a[now].x<=t[i]) pq.push(a[now++]);
while(!pq.empty()&&pq.top().y<t[i]) pq.pop();
if(!pq.empty()) ans++,pq.pop();
}
cout<<ans;
return 0;
}
T2
略。
T3
略。
T4
略。
标签:node,sort,15,YL,int,bool,堆中,模拟 From: https://www.cnblogs.com/XOF-0-0/p/18048909