题解 CF950B 【Intercepted Message】

简介: 题目链接 先吐槽一番:本宝宝好久没写过题解了。。。首先我们想一个贪心策咯。就是我们预处理出前缀和,然后一边扫过去,记录一个l1,l2和一个n1,n2。分别表示我们现在第一个数组切到l1,上一次切是在n1处。

题目链接

先吐槽一番:本宝宝好久没写过题解了。。。
首先我们想一个贪心策咯。
就是我们预处理出前缀和,然后一边扫过去,记录一个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
*/

 


如果对大家有帮助的话,希望大家留言支持呦~

相关文章
|
C++
hdoj 4288coder & cf 85d Sum of Medians
这两个题目是一样的,大概题意是有3个操作 add x, 在集合中加入x, del x 是删除x, sum 是求出由小到大排序后所有下标mod5等于3的数的和。
32 0
CF219A k-String(数学分析)
CF219A k-String(数学分析)
64 0
|
机器学习/深度学习 人工智能 算法
CF1550A Find The Array(贪心算法)
CF1550A Find The Array(贪心算法)
36 0
|
算法 应用服务中间件 AHAS
CF1321C Remove Adjacent(周围串删除)(贪心算法)
CF1321C Remove Adjacent(周围串删除)(贪心算法)
52 0
|
存储 算法 安全
LeetCode - #2 Add Two Numbers
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #2 Add Two Numbers
|
人工智能
CF1660C Get an Even String(贪心)
CF1660C Get an Even String(贪心)
99 0
leetcode 649 Data2 参议院
leetcode 649 Data2 参议院
69 0
|
BI
CF1367 D. Task On The Board(构造)
CF1367 D. Task On The Board(构造)
82 0
组装数据- 对象里面是key:value, value里面是数组的形式,如 {key:[aa,bb], key:[cc,dd]}
组装数据- 对象里面是key:value, value里面是数组的形式,如 {key:[aa,bb], key:[cc,dd]}
组装数据- 对象里面是key:value, value里面是数组的形式,如 {key:[aa,bb], key:[cc,dd]}
|
程序员 C++ 开发者
​在VS Code中,完成所有你想做的!
在VS Code中,完成所有你想做的!
​在VS Code中,完成所有你想做的!