浮水法-POJ2528

浮水法

简单来说就是水上浮着n条线段，由下至上上浮，浮到一半有重叠了就换其中一半继续浮。

————————————1
       ——————————2
 ——3
                  ——————————4
————————————————————5
                          _________6

如图6上浮，5无重叠，上浮，5有重叠，截去一半继续浮，之后上浮没有阻碍

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
#define debug printf("*");
//#define mo 1e9+7
const int N=10010;
int c,n;
int l[N],r[N];
int iffloat(int L,int R,int bh){
    while(bh<=n&&(r[bh]<L||R<l[bh])) bh++; 
    if(bh>n) return 1;
    if(l[bh]<=L&&R<=r[bh]) return 0;//被吃了 
    
    bool flag=0;
    if(L<l[bh]) flag=iffloat(L,l[bh]-1,bh+1);//吃了别人 
    if(flag==0&&r[bh]<R) flag|=iffloat(r[bh]+1,R,bh+1);
    return flag;
}
int main(){
    scanf("%d",&c);
    while(c--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&l[i],&r[i]);
        int ans=0;
        for(int i=1;i<=n;i++){
            if(iffloat(l[i],r[i],i+1)) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

浮水法-POJ2528

原文：https://www.cnblogs.com/zdsrs060330/p/12490458.html