题目连接
题意
给定长度为n的数列A和数列B，利用已经存在的两数列A,B生成A数列的后续
an+1,an+2,......,a2n
项，要求生成的新的项时满足条件
ai≤max{aj−j∣bk≤j<i}
,式中k为所选用的数，每个
bk
限定只能选一次。求取
max{∑2nn+1ai}
。
分析
要求取最大值，显然
ai=max{aj−j∣bk≤j<i}
,问题转换成了如何分配k使得最后和最大。假定
ap−p≤aq−q
对于所有的
p<q
成立，
at−t≤aq−q
对于所有的
t>q
成立。那么对于所有的
bk≤q
显然生成的数均为
aq−q
，考虑到所有生成的数
ai
对后续的影响为
ai−i
,想要使得后续的数尽可能的大，由于
ai
固定不变，则在
i
最小时ai−i最大。所以可以贪心的采用每次生成的数均为可行方案中最大的结果，最后求取
∑2nn+1ai
的结果必然也是最大值。比赛期间使用的优先队列来快速寻找到最大的数，然后用树状数组记录
bk
的值，快速能够生成的
ai
的具体数列。赛后发现其实想多了，不需要使用树状数组，一个前缀和就可以获取具体数量了。具体可以看看比赛时的代码
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
#define LL long long
#define MAXN 250250
const int mod=
1e9+
7;
struct Node{
int v,idx;
Node(
int _v,
int _idx):v(_v),idx(_idx){}
Node(){}
friend bool operator<(Node n1,Node n2){
if(n1.v!=n2.v)
return n1.v<n2.v;
return n1.idx<n2.idx;
}
};
int bin[MAXN];
int a[MAXN];
int b[MAXN];
int lowbit(
int x){
return x&-x;
}
int sum(
int x){
int ret=
0;
while(x){
ret+=bin[x];
x-=lowbit(x);
}
return ret;
}
int add(
int x){
while(x<MAXN){
bin[x]++;
x+=lowbit(x);
}
}
int query(
int x,
int y){
return sum(y)-sum(x-
1);
}
int main(){
int n;
while(~
scanf(
"%d",&n)){
priority_queue<Node> q;
memset(bin,
0,
sizeof(bin));
for(
int i=
1;i<=n;++i){
scanf(
"%d",&a[i]);
q.push(Node(a[i]-i,i));
}
for(
int i=
1;i<=n;++i){
scanf(
"%d",&b[i]);
add(b[i]);
}
LL ans=
0;
int res=n,mx=
0,pos=n+
1;
while(res && !q.empty()){
Node tmp=q.top();
q.pop();
if(tmp.idx<=mx)
continue;
if(tmp.idx>mx){
if(tmp.idx>n){
ans+=tmp.v*
1ll*res;
res=
0;
continue;
}
else{
int num=query(mx+
1,tmp.idx);
ans+=tmp.v*
1ll*num;
q.push(Node(tmp.v-pos,pos));
pos+=num;
res-=num;
mx=tmp.idx;
continue;
}
}
}
ans%=mod;
printf(
"%I64d\n",ans);
}
}
