HPU personal training

K - Two Contests

原题链接：https://agc040.contest.atcoder.jp/tasks/agc040_b?lang=en

题目大意：

给一个区间集合，将这些区间分为两个集合，求两个区间中线段交集的最大值。

解题思路：

首先找到这些区间的右端点在最左端的区间p，左端点在最右端的区间q。

如果p，q在同一个集合中，那么这个集合的最大交集就是p_r - q_l，而另一个只放一个最大的区间，得到ans1。
如果不在同一个区间，想一下集合区间的特征，含有p的集合S中，区间的右端点都大于p的右端点，那么他们的最大交集就是p_R - min_L{ L属于集合S} + 1，含有q的集合T中，区间的左端点都小于q的左端点，那么他们的最大交集就是min_R{R属于集合T} - q_l + 1.可以知道如果直接从所有集合中找最合适期间，那么找到的这个区间可能既在S集合中又在T集合中，所以不能这样找。因此要用到后缀最小值。首先对于每一个区间存储R-mxl+1和mnR-L+1两个数据。然后按其中一个数据对数组排列大小，（要从大的开始，因为大的在一个集合中，所有比他小的都在另一个集合中，然后从大到小找两个集合中的最小交集，这样就可以用后缀最小值了。）

代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 1e5 + ;

 struct aa{

     int first,second;

 }P;

 aa arr[N];//记录区间

 int minnore[N];

 aa S[N];

 bool cmp1(aa a, aa b){

     return a.first > b.first;

 }

 int main(){

     int q, L, R, mxL = , mnR = 1e9 + , RR, LL;

     int flag1 = , flag2 = , maxlen = ;

     scanf("%d", &q);

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

         scanf("%d%d", &L, &R);

         arr[i].first = L;

         arr[i].second = R;

         if(L > mxL){

             mxL = L;

             RR = R;

             flag1 = i;

         }

         if(R < mnR){

             mnR = R;

             LL = L;

             flag2 = i;

         }

         maxlen = max(maxlen, R - L + );

     }

     int ans1 = maxlen;

     if(mnR >= mxL)    ans1 += mnR - mxL + ;

     if(flag1 == flag2){

         cout << ans1 << endl;

         return ;

     }

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

         S[i].first = max(arr[i].second - mxL + , );

         S[i].second = max(mnR - arr[i].first + , );

     }

     sort(S, S + q, cmp1);

     minnore[q-] = S[q - ].second;

     for(int i = q - ; i >= ; i --){

         minnore[i] = min(minnore[i + ], S[i].second);

     }

     int ans2 = ;

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

         ans2 = max(ans2, S[i].first + minnore[i+]);

     }

     cout << max(ans2,ans1) <<endl;

     return ;

 }

巴特西

HPU personal training

K - Two Contests

最新文章

热门文章