AcWing 906. 区间分组
原题链接
简单
作者:
Yaseal
,
2023-07-16 14:44:02
,
所有人可见
,
阅读 75
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100010
typedef struct node{
int a,b;
}Node;
Node u[100010];
int heap[100010],hsize=0;
int getTop(){
return hsize>0?heap[1]:-1;
}
void up(int idx){
int t=idx>>1;
if(t==0) return ;
if(heap[t]>heap[idx]){
int tmp=heap[idx];
heap[idx]=heap[t];
heap[t]=tmp;
up(t);
}
}
void down(int idx){
int t1=idx<<1;
int t2=(idx<<1)+1;
int t;//确定到底要和哪一个元素交换,避免重复交换
if(t1<=hsize&&t2<=hsize){
if(heap[t1]<heap[t2]){
t=t1;
} else{
t=t2;
}
} else if(t1<=hsize){
t=t1;
} else{
return;
}
if(heap[t]<heap[idx]){
int tmp=heap[idx];
heap[idx]=heap[t];
heap[t]=tmp;
down(t);
}
}
void push(int x){
heap[++hsize]=x;
up(hsize);
}
int pop(int x){
int ret=heap[1];
heap[1]=heap[hsize--];
down(1);
return ret;
}
int cmp(const void *a,const void *b){
Node *n1=(Node *)a;
Node *n2=(Node *)b;
return n1->a-n2->a;
}
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&u[i].a,&u[i].b);
}
qsort(u,n,sizeof(Node),cmp);
for(int i=0;i<n;i++){
if(i==0){
push(u[i].b);
continue;
}
int m=getTop();
if(m>=u[i].a){
push(u[i].b);
} else{
heap[1]=heap[1]>u[i].b?heap[1]:u[i].b;
down(1);
}
}
printf("%d",hsize);
return 0;
}
- C语言版本,注意堆的up和down的操作逻辑,记得用递归调用