李XX又鸽了今晚的CF之营长生气了!

发布于 2019-06-07  71 次阅读


李XX又鸽了今晚的CF之营长生气了!

题目

  • 今天,作为书店老板的营长有一家店打算试营业 n 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。
    在某些时候,营长会生气(因为李XX又咕咕咕了CF比赛)。 如果营长在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当营长生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。
  • 营长知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。
  • 请你返回这一天营业下来,最多有多少客户能够感到满意的n数量。

输入

  • 输入一个n 代表有 n分钟, 一个 x (营长能够连续不生气的时间)
  • 接下来一行有 n 个customers[i] 代表第i 分钟有 customers[i] 个 顾客
  • 接下来一行 有 n个grumpy[i] 代表 第 i 分钟 营长的情绪状况

  • 1 <= X <= n <= 20000

  • 0 <= customers[i] <= 1000
  • 0 <= grumpy[i] <= 1

输出

  • 输出最多的满意度

样例输入

  • 8 3
  • 1 0 1 2 1 1 7 5
  • 0 1 0 1 0 1 0 1

样例输出

  • 16

思路

  • 首先理解题意,先把不生气的满意度算好,再触发营长的技能 过滤之前加过的满意度,找到最大区域段

代码

#include <cstdio>
#include <algorithm>
using namespace std;
int customers[20010];
int grumpy[20010];
int main()
{
    int n,x;
    long long sum=0;
    scanf("%d%d",&n,&x);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&customers[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&grumpy[i]);
    }
    for(int i=0;i<n;i++)
    {
        if(!grumpy[i])
        {
            sum+=customers[i];
        }
    }
    long long _max = -1,_sum;
    for(int i=0;i<n;i++)
    {
        if(grumpy[i])
        {
            _sum = 0;
            for(int j=0;j<x;j++)
            {
                if(i+j>n)
                     break;
                if(grumpy[i+j])
                    _sum+=customers[j+i];
            }
            _max = max(_sum,_max);
        }
    }
    sum+=_max;
    printf("%lld\n",sum);
    return 0;
}

水过~~~


还是好热爱web开发