讨论/《春招冲刺班 - 7 天刷题挑战》 - 发下午茶/
《春招冲刺班 - 7 天刷题挑战》 - 发下午茶
共 9 个回复
#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1010;
int arr[MAXN], tmp[MAXN];
int n, m;

bool check(int mid){
    memcpy(tmp, arr, sizeof(tmp));

    for(int i = 0, j = m; i < n; i ++){
        int t = mid - j;
        while(t){
            if(t >= tmp[j]){
                t -= tmp[j];
                j --;
                if(! j)
                    return true;
            }else{
                tmp[j] -= t;
                t = 0;
            }
        }
    }
    return false;
}

int main(){
    int a;

    cin >> n >> m;

    for(int i = 1; i <= m; i ++){
        cin >> arr[i];
    }

    int le = m, ri = 1e7 + 10, mid;
    while(le < ri){
        mid = le + ri >> 1;
        if(check(mid))
            ri = mid;
        else
            le = mid + 1;
    }
    cout << ri << endl;
    return 0;
}
2

二分找最小时间T,使得K名字节君能在T时间内投放完所有区域的下午茶。

import java.util.*;

public class Solution {

    static int size;

    static boolean check(int k,int time,int[] cnt)
    {
        int n = cnt.length-1;
        int cur = 1;
        int used = 1;
        int rest = time;        //记录员工的剩余行动次数
        while(cnt[size]!=0)
        {
            for(int i = 1;i<=size;i++)
            {
                rest-=1;    //前进一个区域消耗1次移动次数
                if(cnt[i]==0)continue;  //当前区域不需要下午茶,往后走
                if(rest<=0){used+=1;rest = time;break;}      //走不到区域i,换新人

                //派送下午茶
                if(rest>=cnt[i]){       //行动力够
                    rest-=cnt[i];
                    cnt[i]=0;
                }    
                else {                  //行动力不够,下一位继续
                    cnt[i]-=rest;
                    used+=1;
                    rest = time;break;
                }
            }
        }

        if(used<=k)return true;
        return false;

    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        int n = scanner.nextInt();
        size = n;
        int[] cnt = new int[n+1];

        for(int i=1;i<=n;i++)cnt[i]=scanner.nextInt();
        while(size>0&&cnt[size]==0)size-=1;     //如果末尾区域需要的下午茶份数为0,那么它其实可以被忽略

        int[] copy = new int[size+1];
        for(int i=1;i<=size;i++)copy[i] = cnt[i];
        int l = size+1;     //走到最后一个区域size至少需要size步
        int r = 100000000;
        while(l<=r)
        {
            int mid = (l+r)>>1;
            if(check(k,mid,copy)==true){r = mid-1;}
            else l = mid+1;
            for(int i=1;i<=size;i++)copy[i] = cnt[i];
        }
        System.out.println(l);


    }
}

1
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
int TT[MAXN];
int T[MAXN];
int K, N;

bool check(int k, int mid){
     memcpy(T, TT, sizeof T);
     int i = N - 1;
     while(k){
         int tmp = mid - (i + 1);
         if(tmp < 0) {
             return false;
         }
         while(tmp >= 0){
             if(tmp >= T[i]){
                 tmp -= T[i];
                 --i;
                 if(i < 0) return true;
             }else{
                 T[i] -= tmp;
                 k--;
                 break;
             }
         }
     }
     return false;
 }

int main(){
    cin>>K>>N;
    for(int i=0; i < N; ++i) cin>>TT[i];
    int len = 1e7 + 50;
    int left = 0, right = len;
    while(left < right){
        int mid = (left + right) / 2;
        if(check(K, mid)){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    cout<<left;
    return 0;
}

参照评论区dalao的java解法用 python实现一遍

要求的目标是最少动作次数,花费动作次数从1... n 递增,呈现线性关系所以使用二分查找,寻找最小次数;对每个次数模拟送下午茶的过程

def check(time, arr):
    cnt = arr[:]
    start = -1
    flag = False
    for i in range(k):
        move = time
        cur = start + 1
        move = time - cur
        for j in range(cur, n):
            move -= 1
            if move == 0:
                break
            if cnt[j] == 0:
                start = j
                continue
            if cnt[j] > move:
                cnt[j] -= move
                break
            else:
                move -= cnt[j]
                cnt[j] = 0
            if cnt[n-1] == 0:
                flag = True
                break
    return flag


def solution():
    lo, hi = MINTIME, MAXTIME
    while lo < hi:
        mid = (hi + lo) >> 1
        # print(lo, hi, mid)
        if check(mid, nums):
            hi = mid
        else:
            lo = mid + 1
    return lo


k, n = map(int, list(input().strip().split(" ")))
nums = list(map(int, list(input().strip().split(" "))))
MAXTIME = 1000 * 10000
MINTIME = 2
if __name__ == "__main__":
    res = solution()
    print(res)

r只要大于等于最大的可能时间t,取多少都可以。当字节君数量K取最小值1,N取最大值1000,Ti取最大值10000,花费的时间t会是1000*10000+1000。取r=10001000是最优的选择,取更大的r不会影响结果,但会增加迭代次数。

int r = 100000000;
100000000怎么来的?

你好,你只是忘了初始化t数组而已,你的代码是可以AC的,而且十分简洁。

厉害,可以看一下我下面的代码吗?

import java.util.Scanner;
public class Solution {
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int k=sc.nextInt();
int n=sc.nextInt();
int[]t=new int[n];
int res=solve(t,k);
System.out.println(res);
}

private static int solve(int[] t, int k) {
// TODO Auto-generated method stub
int l=0,r=20000000;
while (l+1<r) {
int mid=(l+r)/2;
if (check(t,k,mid)) {
r=mid;
}else {
l=mid;
}
}
return check(t, k, l)?l:r;
}

private static boolean check(int[] t, int k, int limit) {
// TODO Auto-generated method stub
int workspace=0,index=0;
for (int i = 0; i < k; i++) {
int left=limit-workspace-1;
while (left>0&&workspace<t.length) {
int count=Math.min(left, t[workspace]-index);
left-=count;
index+=count;
if (index==t[workspace]) {
workspace++;
index=0;
left--;
}
}
}

return workspace==t.length;

}
}