P2887 [USACO07NOV] Sunscreen G
将奶牛按照 \(minn[i]\) 从大到小排序，对于任意一个奶牛，如果存在一个适合于他且 \(spa\) 值尽量大的防晒霜，就用它；否则这个奶牛不用防晒霜。时间复杂度\(O(n^2)\)。
\(code:\)
bool cmp(node a,node b){
return a.l>b.l;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].l,&a[i].r);
for(int j=1;j<=m;++j)
scanf("%d%d",&b[j].w,&b[j].num);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i){
int maxn=0,id=0;
for(int j=1;j<=m;++j)
if(b[j].w>=a[i].l&&b[j].w<=a[i].r&&b[j].num){
if(b[j].w>maxn)
maxn=b[j].w,id=j;
}
if(id){
++ans;
--b[id].num;
}
}
printf("%d\n",ans);
return 0;
}
P2859 [USACO06FEB] Stall Reservations S
将每一个区间以左端点的值为关键字，从大到小排序。
设 \(a_j\) 表示第 \(j\) 个小组最靠右的区间的右端点。对于第 \(i\) 个区间，如果能放入小组 \(j\) ，那么 \(a_j<l_i\) 。因此只需要判断最小的 \(a_j\) 是否小于 \(l_i\) ，如果符合，就直接把 \(i\) 放入小组 \(j\) ；否则新建一个小组。
用小根堆维护上述小组，时间复杂度 \(O(n\) \(logn)\)
\(code:\)
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].l,&a[i].r),a[i].num=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i){
if(q.empty()||q.top().w>=a[i].l){
q.push((que){++tot,a[i].r});
b[tot].push_back(a[i].num);
}
else{
int now=q.top().id;
q.pop();q.push((que){now,a[i].r});
b[now].push_back(a[i].num);
}
}
printf("%d\n",tot);
for(int i=1;i<=tot;++i)
for(int j=0;j<b[i].size();++j)
at[b[i][j]]=i;
for(int i=1;i<=n;++i)
printf("%d\n",at[i]);
return 0;
}