最大覆盖问题_前缀长度24是什么意思怎么调

2531 最大覆盖

 

现在有 nn 个位置 1…n1…n 。

给qq个区间，请你选出选q−2q−2个，使得覆盖位置个数最大。

 收起

输入

第一行两个数n,q(3<=n,q<=5000)。
接下来q行，其中第i行两个数l[i],r[i]，表示第i个区间能覆盖所有满足l[i]<=x<=r[i]的位置x。

输出

一个数表示最大值。

输入样例

4 3
1 1
2 2
3 4

输出样例

2

该题目前两种可行思路：

1、正向考虑：选q-2个区间，将所有区间按照区间长度从大到小排序，

每次选择最长的一个区间，选择后将该区间覆盖的区域设定为“无效状态”，

然后更新其他区间的覆盖长度（这里可以前缀和优化，左到单个区间更新O（1）），

重新排序后再选择最长。时间复杂度O(N*NlogN)，NlogN是排序时间复杂度。

2、逆向考虑：

去掉两个影响最小的：

求出整个区间N上每个 区间内点均-1所产生影响，-2产生的影响（前缀和），

两两枚举题目所给区间，根据是否相交计算影响，选择最小值，作为最终答案。

代码实现（方案2）：

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<set>
#include<algorithm>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e5+100;
const int M=4e5+100;
pair<int,int>arr[N];
int vis[N];
LL pre[5000+10],sum[5000+10];
int main()
{
  int n,q;
  LL ans=0,mini;
  while(cin>>n>>q)
  {
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    memset(sum,0,sizeof(sum));
    ans=0;
    mini=INF;
    for(int i=1; i<=q; i++)
    {
      cin>>arr[i].first>>arr[i].second;
      for(int j=arr[i].first; j<=arr[i].second; j++)
      {
        if(!vis[j])ans++;
        vis[j]++;
      }
    }
    for(int i=1; i<=n; i++)
    {
      pre[i]=pre[i-1]+(int(vis[i]-1>0)^1);
      sum[i]=sum[i-1]+(int(vis[i]-2>0)^1);
    }

    for(int i=1; i<=q; i++)
    {
      for(int j=i+1; j<=q; j++)
      {
        int l1=arr[i].first,l2=arr[j].first;
		int r1=arr[i].second,r2=arr[j].second;
        if(max(l1,l2)<=min(r1,r2))
        {
          mini=min(mini,pre[r1]-pre[l1-1]+pre[r2]-
		  		pre[l2-1]+sum[min(r1,r2)]-sum[max(l1,l2)-1]);
        }
        else
        {
          mini=min(mini,pre[r2]-pre[l2-1]+pre[r1]-pre[l1-1]);
        }
      }
    }
    cout<<ans-mini<<endl;
  }
  return 0;
}

方案一（别人代码）：

#include<iostream>
#include<algorithm>

using namespace std;

struct Node {
	int l,r,cs;
} p[10000];

int vis[10000],b[100000];

bool cmp(Node x,Node y) {
	return x.cs>y.cs;
}

int main() {
	int n,q;
	cin>>n>>q;
	for(int i=0; i<q; i++) {
		cin>>p[i].l>>p[i].r;

	}
	for(int i=0; i<=n; i++) {
		vis[i]=1;
	}
	int ans=0;
	for(int i=0; i<q-2; i++) {
		b[0]=vis[0];
		for(int k=1; k <= n; k++)
			b[k]=b[k-1]+vis[k];
		for(int k =0 ; k < q; k++) {
			p[k].cs=b[p[k].r] - b[p[k].l-1];
		}
		sort(p,p+q,cmp);
		for(int k=p[0].l; k<=p[0].r; k++)
			if(vis[k]) {
				ans++;
				vis[k]=0;
			}
	}
	cout<<ans<<endl;
	return 0;
}

THE END

今天的文章最大覆盖问题_前缀长度24是什么意思怎么调分享到此就结束了，感谢您的阅读。