Wunder Fund Round 2016 (Div. 1 + Div. 2 combined) F. Double Knapsack(构造)

题目

思路来源

namomoCamp的ppt

https://www.cnblogs.com/cjyyb/p/10575154.html

题解

可以二分，

但由于两个序列单增的性质，所以可以双指针，

想实现的优雅一点，于是参考了yyb的博客

代码

#include 
using namespace std;
typedef long long ll;
#define pb push_back
const int N=1e6+10;
int n;
ll a[N],b[N];
int pa[N],pb[N];//posa[],posb[]
bool swp;
//(l,r]
void out(int l1,int r1,int l2,int r2){if(swp){swap(l1,l2);swap(r1,r2);}printf("%d\n",r1-l1);for(int i=l1+1;i<=r1;++i){printf("%d%c",i," \n"[i==r1]);}printf("%d\n",r2-l2);for(int i=l2+1;i<=r2;++i){printf("%d%c",i," \n"[i==r2]);}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%lld",&a[i]);a[i]+=a[i-1];}for(int i=1;i<=n;++i){scanf("%lld",&b[i]);b[i]+=b[i-1];}if(a[n]>b[n]){swap(a,b);swp=1;}int x=0;memset(pa,-1,sizeof pa);for(int i=0;i<=n;++i){while(x+1<=n && b[x+1]<=a[i]){x++;}int r=a[i]-b[x];//remainderif(~pa[r]){out(pa[r],i,pb[r],x);return 0;}pa[r]=i;pb[r]=x;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！