題解 CF950B 【Intercepted Message】

題目連結

先吐槽一番：本寶寶好久沒寫過題解了。。。

首先我們想一個貪心策咯。

就是我們預處理出字首和，然後一邊掃過去，記錄一個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
*/      

如果對大家有幫助的話，希望大家留言支援呦~