增援前线

(20) 分做法

考虑暴力。答案为(a_i)的和

(50) 分做法

枚举全排列

(100) 分做法

我们可以用二分法或贪心。

这里会用到一个性质。

说人要尽量走得远一点。什么意思？为什么？

画一个图：

假设：(L=4)

比如说这个魂师，他有 (2) 种选择，现在我们的结论是走最远的最优。

那么，我们看他走近的

都没路走了，只能还是走远端的那片叶子，所以相当于浪费了一片叶子。

走远的

还能走，那么我想用这个例子说明什么呢？

我们走得越远，选择越多。

从贪心的角度来讲，要让所有魂师消耗的叶子数量尽量少。

二分

利用刚刚所讲的性质，我们用二分来写。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
    T RR=1;FF=0;char CH=getchar();
    for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
    for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
    FF*=RR;
}
template<typename T>inline void write(T x){
    if(x<0)putchar('-'),x*=-1;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
template<typename T>inline void writen(T x){
    write(x);
    puts("");
}
int l,r=1,a[100010],b[100010],L,n;//左闭右开，r=1
bool check(int mid){
    memset(b,0,sizeof(b));//a[i]表示的是每个格子的上限，b[i]表示的是每个格子现有的数量
    b[0]=mid;a[n]=mid;
    for(int i=0;i<n;i++){
        for(int j=min(i+L,n);j>=i+1;j--)//从远的开始试
            if(b[j]<a[j]){
                if(b[j]+b[i]<=a[j]){//全部都能去，那么就全部都去
                    b[j]+=b[i];//移走
                    b[i]=0;//变成零
                    break;
                }else{
                    b[i]-=a[j]-b[j];//能塞，尽量塞
                    b[j]=a[j];//塞满
                }
            }
        if(b[i]!=0)return false;//有人没去处，就代表不可能
    }return true;//可能
}
int main(){
    read(n);read(L);
    for(int i=1;i<n;i++){
        read(a[i]);
        r+=a[i];
    }
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid))l=mid;
        else r=mid;
    }cout<<l;
    return 0;
}

贪心

我们发现，上面的二分似乎没什么用，知道答案也未必更好算。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
    T RR=1;FF=0;char CH=getchar();
    for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
    for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
    FF*=RR;
}
template<typename T>inline void write(T x){
    if(x<0)putchar('-'),x*=-1;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
template<typename T>inline void writen(T x){
    write(x);
    puts("");
}
int a[100010],b[100010],L,n,s;
int main(){
    read(n);read(L);
    for(int i=1;i<n;i++){
        read(a[i]);
        s+=a[i];//一样的道理
    }
    b[0]=s;a[n]=s;//拿边界
    for(int i=0;i<n;i++){
        for(int j=min(i+L,n);j>=i+1;j--)//从远的开始试
            if(b[j]<a[j]){
                if(b[j]+b[i]<=a[j]){//全部都能去，那么就全部都去
                    b[j]+=b[i];//移走
                    b[i]=0;//变成零
                    break;
                }else{
                    b[i]-=a[j]-b[j];//能塞，尽量塞
                    b[j]=a[j];//塞满
                }
            }
    }cout<<b[n];
    return 0;
}