http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1672
收藏
关注第一行三个数n,k,m(1<=n<=100000,1<=k<=m<=100000)。 接下来一行n个数ai，表示小A的数列(0<=ai<=10^9)。 接下来m行，每行两个数li,ri，表示每个区间(1<=li<=ri<=n)。
一行表示答案
5 2 3 1 2 3 4 6 4 5 2 5 1 4
10
简化版的是求两个区间相交的最大值，而这个求k个区间相交的最大值，前者是维护一个最大的右端点同理，我们维护k个较大的右端点就好了。
先按照左端点升序排列，这样的话固定了左端点只考虑右端点就好了，每次询问一个区间找到当前队列中右端点最小的那个做交集，之后再判断要不要把当前右端点加入如果更优的话。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 priority_queue<int,vector<int>,greater<int> >q; 5 LL A[100005]; 6 struct node{int l,r;}P[100005]; 7 bool cmp(node A,node B) 8 { 9 if(A.l!=B.l) return A.l<B.l; 10 else return A.r>B.r; 11 } 12 int main() 13 { 14 int n,m,k,i,j; 15 LL ans=0; 16 while(cin>>n>>k>>m){ 17 for(i=1;i<=n;++i) scanf("%lld",&A[i]),A[i]+=A[i-1];A[n+1]=A[n]; 18 for(i=1;i<=m;++i) scanf("%d%d",&P[i].l,&P[i].r); 19 if(k==1){ 20 for(i=1;i<=m;++i) 21 ans=max(ans,A[P[i].r]-A[P[i].l-1]); 22 } 23 else{ 24 sort(P+1,P+1+m,cmp); 25 for(i=1;i<=m;++i) 26 { 27 if(q.size()<k-1) q.push(P[i].r); 28 else{ 29 ans=max(ans,A[min(q.top(),P[i].r)]-A[P[i].l-1]);//一开始写的q.top()导致WA 30 q.push(P[i].r); 31 q.pop(); 32 } 33 } 34 } 35 printf("%lld\n",ans); 36 } 37 return 0; 38 }
原文：http://www.cnblogs.com/zzqc/p/7462607.html
