标题

黑洞题解

思路

对于每一个维度，会有正反两个方向。总共有 $2^n$ 种方法，确定他的对角线长度取决于所有维度的最小值。所以找到最小值就有一半的方法的答案贡献是最小值，也就是 $2^{n-1}$ 。再找次小值，以此类推。 特别的，当取到两个同维度的，则不需要取一半。

解题方法

使用 $xp$ 数组记录 $2^n$ 对 $mod$ 取余的结果。再存储每一个方向的长度，记录维度，排序。

复杂度

时间复杂度:

$O(nlogn)$

空间复杂度:

$O(n)$

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool b[1000030];
const int mod=1e9+7;
int n,m[1000030],a[1000030],xp[1000030];
struct node{
	int sum,num;
};
bool cmp(node x,node y){
	return x.sum<y.sum;
}
vector<node> v;
signed main(){
//	freopen("hole7.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i];
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v.push_back({a[i]-1,i});
		v.push_back({m[i]-a[i],i});
	}
	sort(v.begin(),v.end(),cmp);
	xp[0]=1;
	for(int i=1;i<=n;i++){
		xp[i]=xp[i-1]*2;
		xp[i]%=mod;
	}
	int idx=n,sum=0;
	for(auto i:v){
		if(b[i.num]){
			sum+=i.sum*xp[idx];
			sum%=mod;
			break;
		}
		else{
			idx--;
			b[i.num]=1;
			sum+=i.sum*xp[idx];
			sum%=mod;
		}
	}
	cout<<(sum+1)%mod;
}