【XSY3678】最大值（贪心，二进制）

题面

题解

贪心。

从高位往低位考虑。

• 首先，如果当前位所有区间都能取到 \(1\)，那么我们就都取 \(1\)。

• 否则，肯定有区间不能取到 \(1\)，所以这一位并出来之后只能为 \(0\)。

  而且当前所有区间可以分成这三类：这一位只能取 \(0\) 的、这一位只能取 \(1\) 的、这一位 \(0\) 和 \(1\) 都能取的。

  对于前两类我们维持不变，对于最后那一类我们这一位全部取 \(0\)，因为此时后面的所有位都能取 \(1\)，肯定最优。

时间复杂度 \(O(n\log V)\)，其中 \(V\) 为值域。

#include<bits/stdc++.h>

#define N 100010
#define ll long long

using namespace std;

int n;
ll l[N],r[N];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&l[i],&r[i]);
	ll ans=0;
	for(int i=62;i>=0;i--)
	{
		ll tmp=(1ll<<(ll)i);
		bool flag=1;
		for(int j=1;j<=n;j++)
			flag&=(r[j]>=tmp);
		if(flag)
		{
			ans+=tmp;
			for(int j=1;j<=n;j++)
			{
				r[j]-=tmp;
				l[j]=max(l[j]-tmp,0ll);
			}
		}
		else
		{
			for(int j=1;j<=n;j++)
			{
				if(l[j]>=tmp) r[j]-=tmp,l[j]-=tmp;
				else if(r[j]>=tmp) r[j]=tmp-1;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}