cf12D Ball（MAP，排序，贪心思想）

题意：

N位女士一起聚在一个舞厅。每位女士有三个特征值B,I,R。分别代表美貌，智慧，富有。

对于一位女士而言，如果存在一个女士的B,I,R都分别大于她自己的B,I,R。则她自己会自杀。

统计总共有多少个女士会自杀。

1 ≤ N ≤ 500000

0 ≤ B_i, I_i, R_i ≤ 10⁹

思路：

这题想不出来。看了题解后觉得很妙。

思想和最长上升子序列的贪心做法有相像的地方。

按B从小到大排，若B相等按I自大到小排，若I相等，按R从小到大排。

*：存在map里的东西（map[key]=val）必有：key1<key2<key3<...　且 val1>val2>val3>... （不存在key[i]<key[j]且val[i]<val[j]，因为<key[i],val[i]>可以去掉）

*边界是个好东西。

代码：

int const N = 500005;

int const oo=1e9+5;

struct node{

    int B,L,R;

}

lady[N];

int n;

bool cmp(node a,node b){

    if(a.B==b.B){

        if(a.L==b.L){

            return a.R<b.R;

        }else{

            return a.L>b.L;

        }

    }

    else{

        return a.B<b.B;

    }

}

map<int,int>  mp;

map<int,int>::iterator it;

int main(){

    cin>>n;

    rep(i,1,n) scanf("%d",&lady[i].B);

    rep(i,1,n) scanf("%d",&lady[i].L);

    rep(i,1,n) scanf("%d",&lady[i].R);

    sort(lady+1,lady+1+n,cmp);

    mp.clear();

    int ans=0;

    mp[-oo]=oo;

    mp[oo]=-oo;

    rep2(i,n,1){

        it=mp.upper_bound(lady[i].L);

        if(it->second>lady[i].R){ //会自杀

            ++ans;

        }

        else{ //不会自杀

            if(mp[lady[i].L]<lady[i].R){

                mp[lady[i].L]=lady[i].R;

                it=mp.lower_bound(lady[i].L);

                --it; //不能丢，不然下面while没有用了，，

                while(it->second<lady[i].R){

                    mp.erase(it--);

                }

            }

        }

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

cf12D Ball（MAP，排序，贪心思想）

最新文章

热门文章