codeforces 1284B. New Year and Ascent Sequence（二分）

B. New Year and Ascent Sequence

题意：定义上升序列Ascent,在一组序列A中，存在1<i<j<n，使得Ai<Aj。现在给定n个序列，求n个序列两两组合的n^2个组合序列中，有多少个组合是Ascent序列。。

思路：用两个MAX,MIN数组分别记录下每个序列的最大值和最小值，然后把最大值进行排序。每次做一遍二分，取每个数组中的最小值到所有数组中的最大值中找有多少个数比它大，这样组合的新序列便是满足Ascent性质。如果本身这个序列就已经满足Ascent的性质，那么直接把最大值设置为9999999，最小值设置为-1存进去。

AC代码：

 #include<iostream>

 #include<vector>

 #include<cstring>

 #include<map>

 #include<algorithm>

 using namespace std;

 vector<int> MAX;

 vector<int> MIN;

 int main(){

     int t;

     cin>>t;

     for(int i = ;i<t;i++){

         int Length;

         cin>>Length;

         long long Min = ;

         long long Max = -;

         int ok = ;

         for(int j = ;j<Length;j++){

             long long cur;

             cin>>cur;

             if(cur> Min && ok == ){

                 ok = ;

             }

             Min = min(Min,cur);

             Max = max(Max,cur);

         }

         if(ok == ){

             MAX.push_back(Max);

             MIN.push_back(Min);

         }

         else{

             MAX.push_back();

             MIN.push_back(-);

         }

     }

     sort(MAX.begin() ,MAX.end() );

     long long ans = ;

     for(int i = ;i<t;i++){

         ans+=(MAX.end() -upper_bound(MAX.begin() ,MAX.end() ,MIN[i]));

         //cout<<ans<<endl;

     }

     cout<<ans;

     return ;

 }

巴特西

codeforces 1284B. New Year and Ascent Sequence（二分）

最新文章

热门文章