51nod 1672 贪心/队列

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1672

1672 区间交 51nod 1672 贪心/队列

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

关注

小A有一个含有n个非负整数的数列与m个区间，每个区间可以表示为li,ri。

它想选择其中k个区间，使得这些区间的交的那些位置所对应的数的和最大。（是指k个区间共同的交，即每个区间都包含这一段，具体可以参照样例）

在样例中，5个位置对应的值分别为1,2,3,4,6，那么选择[2,5]与[4,5]两个区间的区间交为[4,5]，它的值的和为10。

Input

第一行三个数n,k,m(1<=n<=100000,1<=k<=m<=100000)。

接下来一行n个数ai，表示小A的数列(0<=ai<=10^9)。

接下来m行，每行两个数li,ri，表示每个区间(1<=li<=ri<=n)。

Output

一行表示答案

Input示例

Output示例

10

  简化版的是求两个区间相交的最大值，而这个求k个区间相交的最大值，前者是维护一个最大的右端点同理，我们维护k个较大的右端点就好了。
先按照左端点升序排列，这样的话固定了左端点只考虑右端点就好了，每次询问一个区间找到当前队列中右端点最小的那个做交集，之后再判断要不要把当前右端点加入如果更优的话。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL  long long

 priority_queue<int,vector<int>,greater<int> >q;

 LL A[];

 struct node{int l,r;}P[];

 bool cmp(node A,node B)

 {

     if(A.l!=B.l) return A.l<B.l;

     else return A.r>B.r;

 }

 int main()

 {

     int n,m,k,i,j;

     LL ans=;

     while(cin>>n>>k>>m){

     for(i=;i<=n;++i) scanf("%lld",&A[i]),A[i]+=A[i-];A[n+]=A[n];

     for(i=;i<=m;++i) scanf("%d%d",&P[i].l,&P[i].r);

     if(k==){

         for(i=;i<=m;++i)

             ans=max(ans,A[P[i].r]-A[P[i].l-]);

     }

     else{

     sort(P+,P++m,cmp);

     for(i=;i<=m;++i)

     {

         if(q.size()<k-) q.push(P[i].r);

         else{

             ans=max(ans,A[min(q.top(),P[i].r)]-A[P[i].l-]);//一开始写的q.top()导致WA

             q.push(P[i].r);

             q.pop();

         }

     }

     }

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

     }

     return ;

 }

秒客网

51nod 1672 贪心/队列

相关文章