先吐槽一番:本宝宝好久没写过题解了。。。
首先我们想一个贪心策咯。
就是我们预处理出前缀和,然后一边扫过去,记录一个l1,l2和一个n1,n2。
分别表示我们现在第一个数组切到l1,上一次切是在n1处。l2,n2是表示第二个数组。
如果$ans1[l1]-ans1[n1]$ $=$ $ans2[l2]-ans2[n2]$ 就切一刀。(具体见代码)。
否则,如果$ans1[l1]-ans1[n1]$ $>$ $ans2[l2]-ans2[n2]$ 就把l2++。反之,l1++
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int m,n;//长度 int x[1000010]; int y[1000010];//储存序列 int anx[1000010];//前缀和 int any[1000010]; int l1=1,n1;//如上所说, int l2=1,n2;//初始化,l1,l2均为一。n1,n2因为没切过,所以均为0; int ans;//记录答案 int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x[i]); anx[i]=anx[i-1]+x[i]; } for(int i=1;i<=m;i++) { scanf("%d",&y[i]); any[i]=any[i-1]+y[i]; }//输入并处理前缀和。 while(l1<=n&&l2<=m)//判断有没有切完整个序列。 { // printf("%d %d %d %d %d %d\n",l1,n1,l2,n2,(anx[l1]-anx[n1]),(any[l2]-any[n2])); if((anx[l1]-anx[n1])>(any[l2]-any[n2])) l2++; else if((anx[l1]-anx[n1])<(any[l2]-any[n2])) l1++;//如上所说。 else if((anx[l1]-anx[n1])==(any[l2]-any[n2])) { n1=l1;n2=l2;//第一个序列从l1切,第二个从l2切,更新n1,n2; ans++;//答案+1; l1++;//然后继续向后扫。 l2++; } } printf("%d",ans);//输出答案 return 0;//程序拜拜~ } //样例在此 /* 7 6 2 5 3 1 11 4 4 7 8 2 4 1 8 3 3 3 1 10 100 1 100 10 2 1 4 4 1 1 1 1 1 */
如果对大家有帮助的话,希望大家留言支持呦~