3 条题解
信息
- ID
- 82
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 411
- 已通过
- 85
- 上传者
黑洞题解
对于每一个维度,会有正反两个方向。总共有 2n 种方法,确定他的对角线长度取决于所有维度的最小值。所以找到最小值就有一半的方法的答案贡献是最小值,也就是 2n−1 。再找次小值,以此类推。 特别的,当取到两个同维度的,则不需要取一半。
使用 xp 数组记录 2n 对 mod 取余的结果。再存储每一个方向的长度,记录维度,排序。
O(nlogn)
O(n)
#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;
}
sto%%%%%%orz