首页 > 代码库 > 我不管，这就是水题《2》

我不管，这就是水题《2》

2024-10-03 11:46:39   216人阅读

有长度为n的街道  有m个人  大家一起捡垃圾

下面有n个整数a[i]，表示在第i点有a[i]个垃圾

我们在起点0处 没前进一步需要1秒，一次只能捡一个垃圾并且耗时1秒

问你最快需要多少时间能够捡完

输入：

多实例 n,m (0<n<1000)

下面n个整数表示在i位置有多少个垃圾

输出：

最小的耗时

样例输入：

6 2

1 1 1 1 1 1

6 1

1 1 1 1 1 1

样例输出：

8

12

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define N 1006
int n,m,a[N],w[N];
int q(int xx)
{
    int mm=m;
    for(int i=1; i<=n; i++)
        a[i]=w[i];
    while(mm--)
    {
        int x=xx;
        int ans=0;
        for(int i=n; i>=1&&x; i--)
        {
            if(a[i]==0) continue;
            if(ans)
            {
                if(a[i]&&x>=a[i])
                {
                    x=x-a[i];
                    a[i]=0;
                }
                else if(a[i])
                {
                    a[i]=a[i]-x;
                    x=0;
                }
            }
            if(!ans)
            {
                if(a[i]&&x>=a[i]+i)
                {
                    x=x-a[i]-i;
                    a[i]=0;
                }
                else if(a[i]&&x>i)
                {
                    a[i]=a[i]-(x-i);
                    x=0;
                }
                ans=1;
            }
        }
    }

    for(int i=1; i<=n; i++)
    {
        if(a[i])
            return 1;
    }
    return 0;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1; i<=n; i++)
            scanf("%d",&w[i]);
        int l=1,r=INF;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(q(mid))
                l=mid+1;
            else r=mid;
        }
        printf("%d\n",l);
    }
    return 0;
}

 

我不管，这就是水题《2》


联系
我们