当前位置: 代码迷 >> 综合 >> 51nod 1672 区间交 线段树+贪心或优先队列+贪心
  详细解决方案

51nod 1672 区间交 线段树+贪心或优先队列+贪心

热度:64   发布时间:2024-01-15 06:21:58.0

1672 区间交

  1. 1.0 秒
  2.  
  3. 131,072.0 KB
  4.  
  5. 40 分
  6.  
  7. 4级题

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

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

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

 收起

输入

第一行三个数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

 

分析:

线段树:

我们可以先将m组区间按左端点排序。
然后我们依次枚举每个区间,将ri的线段树的位置增加1,这里可以使用线段树进行操作,因为下面我们将枚举左端点,所以直接更新1~ri的即可。
由于ai是非负整数,因此当固定左端点时,右端点一定越远越好(因为答案要求的区间肯定是从左端点起步的,这里你需要在k往上的端点开始寻找,因为至少k次)。
那么问题转换为,寻找一个最远的点x,使得x的值大于等于题目给定的k。这里我们可以在线段树中实现这一操作。

对于查询操作,如果在优先选择往右边跑,如果有边的不够,再去左边找注意要减去右边已经找到的线段。

优先队列:

经典的区间贪心问题,只需要按照左端点排序,然后用优先队列维护,每次将右端点最小的点出队列,队列大小始终保持k即可。
 

#include <bits/stdc++.h>
using namespace std;
#define lson i<<1
#define rson i<<1|1
#define LS l,mid,lson
#define RS mid+1,r,rson
#define ll long long
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define lowbit(x) (x&-x)
struct Node
{int l,r;
} b[N];
ll a[N];
int ans_data;
//注意一定要找一个临时变量记录下ans_***的答案,不然会覆盖
struct node
{int l,r;int data;
} tree[N<<2];void pushup(int i)
{tree[i].data=tree[lson].data+tree[rson].data;
}
//建立线段树
void build(int l,int r,int i)
{tree[i].l = l;tree[i].r = r;if(l == r){tree[i].data =0;return;}int mid = (l+r)>>1;build(LS);build(RS);pushup(i);
}
//tree[l,r]+=val
void add_data(int l,int r,int i,int val)
{if(tree[i].l>=l&&tree[i].r<=r){tree[i].data += val*(tree[i].r-tree[i].l+1);return;}int mid = (tree[i].l+tree[i].r)>>1;if(l<=mid)add_data(l,r,lson,val);if(r>mid)add_data(l,r,rson,val);pushup(i);
}int query(int i,int k)
{if(tree[i].l==tree[i].r){return tree[i].l;}if(tree[i<<1|1].data>=k)query(i<<1|1,k);elsequery(i<<1,k-tree[i<<1|1].data) ;
}
bool cmp(Node x,Node y)
{return x.l<y.l;
}
ll sum[N];
int main()
{int n,k,m;scanf("%d%d%d",&n,&k,&m);for(int i=1; i<=n; i++){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];}for(int i=1; i<=m; i++){scanf("%d%d",&b[i].l,&b[i].r);}sort(b+1,b+m+1,cmp);build(1,n,1);for(int i=1; i<=k; i++){add_data(b[i].r,b[i].r,1,1);}ll ans=0;for(int i=k;i<=m;i++){int pos=query(1,k);ans_data=0;ans=max(ans,sum[pos]-sum[b[i].l-1]);if(i<m)add_data(b[i+1].r,b[i+1].r,1,1);}printf("%lld\n",ans);return 0;
}

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = 100000+5;int n,k,m;
int a[maxn];
ll sum[maxn];priority_queue< int,vector<int>,greater<int> > q;struct node
{int left, right;bool operator< (const node& rhs) const{return left<rhs.left||(left==rhs.left && right<rhs.right);}
}p[maxn];int main()
{while(~scanf("%d%d%d",&n,&k,&m)){sum[0]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}for(int i=0;i<m;i++)scanf("%d%d",&p[i].left,&p[i].right);sort(p,p+m);while(!q.empty())  q.pop();ll ans=0;for(int i=0;i<m;i++){q.push(p[i].right);if(q.size()==k){ans=max(ans,sum[q.top()]-sum[p[i].left-1]);q.pop();}}printf("%lld\n",ans);}return 0;
}