Codeforces Round #390 (Div. 2)

Codeforces Round #390 (Div. 2) - D

阅读量：6118 次

发布时间：2019-06-21

本文共 1988 字，大约阅读时间需要 6 分钟。

题目链接：http://codeforces.com/contest/754/problem/D

题意：给定n个区间，现在让你从这n个区间里面选k个区间，使得这k个区间的交的尽可能的大。

思路：参考HDU 5700区间交。枚举左端点，用multiset维护右端点，因为set自带排序，所以set的第一个元素就是当前最小的右端点，而枚举的i就是当前最大的左端点，然后更新答案。本题的区间会取值会有负数，所以需要离散化一下。另外也可以用线段树来实现。

#define _CRT_SECURE_NO_DEPRECATE#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long int LL;const int MAXN = 3e5 + 10;vector
                 
                  
                   >G[MAXN];pair
                   
                     p[MAXN];LL L[MAXN];int main(){//#ifdef kirito// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);//#endif// int start = clock(); int n,k; while (~scanf("%d%d", &n,&k)){ for (int i = 0; i < MAXN; i++){ G[i].clear(); } for (int i = 0; i < n; i++){ scanf("%I64d%I64d", &p[i].first, &p[i].second); L[i] = p[i].first; } sort(L, L + n); int size = unique(L, L + n) - L; for (int i = 0; i < n; i++){ int idx = lower_bound(L, L + size, p[i].first) - L; G[idx].push_back(make_pair(p[i].second, i + 1)); } LL ans = 0; multiset
                    
                     
                      >se; for (int i = 0; i < size; i++){ for (int j = 0; j < G[i].size(); j++){ se.insert(G[i][j]); } while ((int)se.size()>k){ se.erase(se.begin()); } if ((int)se.size() == k && (se.begin()->first) >= L[i]){ ans =max( se.begin()->first - L[i]+1,ans); } } printf("%I64d\n", ans); if (ans == 0){ for (int i = 1; i <= k; i++){ printf("%d ", i); } } else{ se.clear(); for (int i = 0; i < size; i++){ for (int j = 0; j < G[i].size(); j++){ se.insert(G[i][j]); } while ((int)se.size()>k){ se.erase(se.begin()); } if ((int)se.size() == k&& se.begin()->first >= L[i] && (se.begin()->first - L[i] + 1) == ans){ for (multiset
                      
                       
                        >::iterator it = se.begin(); it != se.end(); it++){ printf("%d ", it->second); } break; } } } printf("\n"); }//#ifdef LOCAL_TIME// cout << "[Finished in " << clock() - start << " ms]" << endl;//#endif return 0;}

转载于:https://www.cnblogs.com/kirito520/p/6262396.html

你可能感兴趣的文章